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

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

15989번: 1, 2, 3 더하기 4

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

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

입력

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

출력

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

문제풀이

import sys

t=int(sys.stdin.readline())
for _ in range(t):
    n=int(sys.stdin.readline())
    if n>3:
        dp = [[0] * (4) for _ in range(n + 1)]
        dp[1][1] = 1
        dp[2][1] = 1
        dp[2][2] = 1
        dp[3][1] = 1
        dp[3][2] = 1
        dp[3][3] = 1
        for i in range(4, n+1):
            dp[i][1]=dp[i-1][1]
            dp[i][2]=dp[i-2][1]+dp[i-2][2]
            dp[i][3]=dp[i-3][1]+dp[i-3][2]+dp[i-3][3]
        print(dp[n][1]+dp[n][2]+dp[n][3])
    else:
        if n==1:
            print(1)
        elif n==2:
            print(2)
        elif n==3:
            print(3)

• 2차원 배열의 DP를 이용하는 문제다.
• 1,2,3을 이용해서 만들어야 하는 수 n에 대한 dp 배열은 다음과 같이 선언한다.
  • dp[n][1] : n을 만들 수 있는 '1' 만으로 만들어진 조합
  • dp[n][2] : n을 만들 수 있는 2보다 작거나 같은 수들(1,2)로 만들어진 조합이면서 '2'로 끝나는 조합
  • dp[n][3] : n을 만들 수 있는 3보다 작거나 같은 수들(1,2,3)으로 만들어진 조합이면서 '3'으로 끝나는 조합
  • 그 이유는 '1+1+2','1+2+1', '2+1+1'처럼 같은 수들로 이루어진 조합을 중복해서 카운팅하지 않기 위해서이다.
  • 예를 들어, n이 4일 때, dp[4][2]는 2보다 작거나 같은 수들로 만들어진 조합이면서 '2'로 끝나야 하기 때문에 '1+1+2'만 세어준다.
• 이제 점화식을 세워서 문제를 풀 수 있다.
• dp[n][1]=dp[n-1][1]
  • 예를 들어, dp[3][1]은 '1+1+1'로 하나 뿐인데, dp[4][1]도 여기에 1을 더한 '1+1+1+1' 하나 뿐이다. 
  • dp[n][1]에는 1로만 이루어진 조합 단 하나만 가능하다. 
• dp[n][2]=dp[n-2][1]+dp[n-2][2]
  • 예를 들어, dp[2][1]의 경우는 '1+1', dp[2][2]의 경우는 '2'가 올 수 있다.
  • 여기서 dp[4][2]='1+1+2', '2+2' 이다.
  • 마지막에 2로 끝나는 경우의 수를 구하려면, n보다 2만큼 작은 수의 1 또는 2로 끝나는 경우에 +2를 해주는 경우만 가능하기 때문에, n보다 2만큼 작은 수의 1 또는 2로 끝나는 경우의 수를 합친 것과 같다.
• dp[n][3]=dp[n-3][1]+dp[n-3][2]+dp[n-3][3]
  • 예를 들어, dp[4][1]='1+1+1+1', dp[4][2]='1+1+2' / '2+2', dp[4][3]='1+3' n=4일 때는 총 4개의 경우의 수가 있다. 
  • 그렇다면 dp[7][3]은 '1+1+1+1+3', '1+1+2+3', '2+2+3', '1+3+3'과 같이 위 경우에 +3을 해주는 경우만 가능하기 때문에, n보다 3만큼 작은 수의 모든 경우의 수와 같다. 
• n이 4 이상 되어야 위 점화식을 만족할 수 있기 때문에 n이 0부터 3까지는 경우의 수를 직접 세서 dp 값을 초기화하고 n이 4일 때부터 목표하는 수까지 for문을 돌면서 dp 배열을 채우도록 구현했다.
• 마지막엔 해당 수의 모든 dp 배열을 모두 합한 값을 출력한다.