백준 9095 - 1, 2, 3 더하기 (Python3)

코드

T = int(input())

for _ in range(T):
    n = int(input())

    d = [0] * (n + 1)
    
    # 아래 두 조건문이 없으면 IndexError
    # break가 아니라 continue로 해야 나머지 반복으로
    # 다른 n값에 대한 결과값도 출력
    if n == 1:
        print(1)
        continue
        
    if n == 2:
        print(2)
        continue
    
    d[1] = 1
    d[2] = 2
    d[3] = 4
    
    for i in range(4, n+1):
        d[i] = d[i-1] + d[i-2] + d[i-3]
            
    print(d[n])

문제 해설

동적 프로그래밍 참고

DP 문제이다. 규칙만 파악하면 쉽게 점화식을 세워서 풀 수 있는 문제였다.

• 규칙 : 앞서 나온 3가지 경우의 수 합 == 현재 경우의 수