백준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

3
4
7
10

예제 출력 1

7
44
274

문제 해결

점화식 만들기

여전히 DP 문제는 점화식 만들기에 몰두해야한다.
앞선 게시글에서도 점화식에 대한 얘기가 많았지만 일단 표부터 먼저 작성해야 한다고 생각했다.
("동전 1" 문제와 매우 유사하다고 생각했다.)

(1)
1만 사용하기
1 = 1(1), 2 = 1+1(1), 3 = 1+1+1(1), ... , 9 = 1+1+1+...+1(1)
2까지 사용하기
1 = 1, 2 = 1+1 = 2(2), 3 = 1+1+1 = 1+2 (2), ... , 9 = 1+...+1 = 2 + 1 + .. + 1 = ... = 2+2+2+2+1

그런데 답은 이것이 아니였다.
"동전 1" 문제와 유사하다고 생각했지만, 내가 위에서 적은 방식은 '1+2'와 '2+1'이 같은 방식이라고 여겼을 때의 방법이었다.

두 시간 가량 고민을 했는데, 이 접근 방식은 접근부터 틀렸었다.

참고 블로그 링크
https://great-park.tistory.com/127

1만 사용할 때, 2까지 사용할 때 등으로 나누는 것이 아닌, dp[0]부터, dp[n+1]까지 한 줄(?)로 봐야헸다.

(2)
dp[1] = 1 (1)
dp[2] = 2 = 1+1 (2)
dp[3] = 3 = 1+2 = 2+1 = 1+1+1 (4)
dp[4] = 3+1 = 1+3 = 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1 (7)
이 다음부터는...

원리는 비슷했다.
사실 처음에 고민했던 방법을 사용 못하겠다는 생각을 한 이유는 이랬다.
1만 사용하는 방법에서 dp[3]은 1+1+1이다.
그런데 1,2를 사용하는 방법에서 dp[3] = 2+1 = 1+2 = 1+1+1 인데, 여기서 dp[5]를 만들기 위해서 2를 추가해야하는데, 2를 연산식에 넣는 방식에 따라 개수가 다양해진다.
그 계산식을 찾지 못했다.
그런데 이렇게 생각하면 다르다.

(2)에서 dp[5]를 만들 때, dp[2]에서는 3을 맨 뒤에 추가, dp[3]에서는 2를 맨 뒤에 추가, dp[4]에서는 1을 맨 뒤에 추가한다고 생각하면 된다.
그러면 중복되는 숫자도 사라지고, 정확하게 계산할 수 있다.
dp[i] = dp[i-3] + dp[i-2] + dpi-1 가 된다.

따라서 코드는 다음과 같다.

T = int(input())

for i 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])