[python]백준 9095 풀이

1, 2, 3 더하기

백준 9095 문제 링크

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

1은 1, 2, 3을 이용해서 한가지 경우로 표현할 수 있습니다.

• $1 = 1$

2는 1, 2, 3을 이용해서 2가지 경우로 표현할 수 있습니다.

• $2 = 1+1$
• $2 = 2$

3은 1, 2, 3을 이용해서 4가지 경우로 표현할 수 있습니다.

• $3 = 1+1+1$
• $3 = 1+2$
• $3 = 2+1$
• $3 = 3$

이제 4부터는 1, 2, 3으로만 표현해야 합니다. 문제의 예시처럼 총 7가지 경우로 표현할 수 있습니다.

• $4=1+1+1+1$
• $4=1+1+2$
• $4=1+2+1$
• $4=2+1+1$
• $4=2+2$
• $4=1+3$
• $4=3+1$

5는 표현하려면 많지만 동일한 방법으로 총 13가지 경우가 존재합니다. 너무 많아서 생략합니다.

이렇게 숫자의 관계를 생각해보면 4는 1, 2, 3의 표현수를 합한 것과 결과가 동일합니다. 5역시도 2, 3, 4의 표현수를 합한 것과 결과가 동일합니다. 이는 피보나치 수열처럼 아래와 같은 점화식을 유추할 수 있습니다.

$a_1=1,a_2=2,a_3=4$

$a_i=a_{i-3}+a_{i-2}+a_{i-1}(i\ge4)$

그렇다면 다이나믹 프로그래밍을 통해서 문제를 해결할 수 있습니다.

import sys
input = sys.stdin.readline
# 테스트 케이스 갯수 입력받음
t = int(input())
# 각 케이스 별 반복문 실행
for _ in range(t):
    dp = [0] * 12 # DP테이블 초기화
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    n = int(input())
    for i in range(4, n+1):
        dp[i] = dp[i-3]+dp[i-2]+dp[i-1]
    print(dp[n]) # 정답 출력

+

처음 문제를 보곤 쌩뚱맞은 짓하면서 시간을 날렸는데, 단순하게 각 항의 관계를 찾는게 더 적절할 수도 있을 것 같습니다 ㅠ