BOJ 9095 1, 2, 3 더하기

3941 단어 2021.01.132021.01.13

https://www.acmicpc.net/problem/9471
시간 1초, 메모리 512MB
input :

  • 테스트 케이스의 수 T
  • n (1 <= n < 11)

output :

  • n 을 나타내는 방법의 수 출력.

조건 :

  • n 을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라.

기저사례

n = 0 /////// 0
n = 1 /////// 1
n = 2 /////// 2
n = 3 /////// 4

3을 만들 때. 3 / 2 + 1, 1 + 1 + 1, / 1 + 2
즉 [n = 2] + [n = 1] + 3인 경우를 다 합친 것.

점화식

n = (n - 1) + (n - 2) + (n - 3)

import sys

T = int(sys.stdin.readline())
data = []
for i in range(T):
    num = int(sys.stdin.readline().strip())
    data.append(num)

dp = [0, 1, 2, 4]

for i in range(4, 11):
    dp.append(dp[i - 1] + dp[i - 2] + dp[i - 3])

for i in data:
    print(dp[i])

그리고 sys.stdin.readline().split()을 할 경우엔 '\n' 개행 표시까지 리스트로 만들어 가지고 있기 때문에.
data[0] 해서 append 하던지. 아니면 strip()을 이용하자.

좋은 웹페이지 즐겨찾기