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

문제

정수 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의 합으로 나타내는 방법의 수를 출력한다.

내 풀이

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-3]+dp[i-2]+dp[i-1]
    print(dp[n])

코멘트

처음에는 1, 2, 3으로 쪼개서 더하는 방법도 모르겠는데다가 1+3과 3+1를 다른 케이스 취급한다니 더 정신이 없어서 계속 틀려왔던 문제다.
그런데 다른 풀이를 보고 나니 1, 2, 3으로 쪼개는 규칙 자체 보다는 그냥 1일 때는 몇이고 2일 때는 몇이고, ... 그렇게 점화식을 찾는 문제였다. 점화식을 찾아보면

dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = 7
dp[5] = 13
dp[6] = 24

와 같이 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 성립함을 알 수 있다. 그래서 그렇게 구하도록 코드를 작성하면 되는데 이때 예외 처리에 주의해야 한다.
처음에는

for i in range(4, n+1):
	dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

과 같이 풀었었는데 이렇게 하면 n이 3 이하인 경우에 대해서 IndexError가 발생하게 되므로 반드시 n이 1, 2, 3일 경우의 예외 처리를 해줘야 한다.

References

https://www.acmicpc.net/problem/9095
https://great-park.tistory.com/127