[Python] 백준 15989 1,2,3 더하기 4

 

문제 분석

• 정수 4를 1,2,3의 합으로 나타내는 방법은 총 4가지가 있다. 
• 합을 나타낼 때에는 수를 1개 이상 사용해야 한다.
• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하라

 

코드 설계

• 순서x, 중복o → 순서가 중요하지 않으니 중복 순열로 뽑 : product
• 중복 조합
• 최대 횟수는 1로만 이루어진 합일 때

 

정답 코드

1차 - 시간 초과

import sys
from itertools import combinations_with_replacement as cr

input = sys.stdin.readline
tc = int(input())

for _ in range(tc) :
    cnt = 0
    n = int(input())
    iter = [1,2,3]

    for i in range(1, n) :
        for num in cr(iter, i) :
            if sum(num) == n :
                cnt += 1
    print(cnt+1)

 

다른 정답 코드 1 : https://soy3on.tistory.com/313

합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. → 점화식만 잘 세우면 

• 1 - 1
• 2 - 1+1; 2
• 3 - 1+1+1; 2+1; 3 
• 4 - 1+1+1+1; 2+2; 2+1+1; 3+1  
• 5 - 1+1+1+1+1; 1+1+1+2; 2+2+1; 2+3; 1+1+3 
• 6 - 1+1+1+1+1+1; 1+1+2+2; 1+1+1+1+2; 1+2+3; 1+1+1+3; 2+2+2; 3+3
• 7 - 1+1+1+1+1+1+1; 1+1+1+1+1+2; 1+1+1+2+2; 1+2+2+2; 1+1+2+3; 1+1+1+1+3; 1+3+3; 2+2+3

import sys
input = sys.stdin.readline

t = int(input())

dp = [1] * 10001

for i in range(2, 10001):
    dp[i] += dp[i - 2]

for i in range(3, 10001):
    dp[i] += dp[i - 3]

for _ in range(t):
    print(dp[int(input())])

 

다른 정답 코드 2 : https://ku-hug.tistory.com/209

dp = [1] * 10001

for i in range(2, 10001):
    dp[i] += dp[i - 2]
    
for i in range(3, 10001):
    dp[i] += dp[i - 3]
    
t = int(input())

for _ in range(t):
    n = int(input())
    print(dp[n])