[백준]9095 1, 2, 3 더하기(Python)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

문제 접근

 

이제는 보자마자 그냥 바로 중복 순열이 떠올랐다. 

 

코드

from itertools import product
T = int(input())

for _ in range(T):
    N = int(input())
    cnt = 0
    for i in range(1, N+1):
        k = list(product([1,2,3],repeat=i))
        for j in k:
            p = sum(list(j))
            if p == N:
                cnt += 1
    print(cnt)

 

++ dp 코드

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    dp = [0] * (N+1)

    for i in range(1, N+1):
        if i == 1:
            dp[i] = 1
        elif i == 2:
            dp[i] = 2
        elif i == 3:
            dp[i] = 4
        else:
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    print(dp[N])

 

회고

 

중복 순열을 사용하면 repeat 사용한다는 점 

 

++ 추가

dp로 풀기 가능

패턴 찾기

dp[1] = 1

dp[2] = 2

dp[3] = 4 :      1+1+1,     1+2,      2+1,      3

dp[4] = 7 :      1+1+1+1,     1+1+2,     1+2+1,     2+1+1,     2+2,     1+3,     3+1

dp[5] = 13 :   1+1+1+1+1,     2+1+1+1(4개),     1+2+2(3개),     1+1+3(3개),     3+2(2개)

...

i >= 4일 때, dp[i] = dp[i-1] + dp[i-2] + dp[i-3]