본문 바로가기

취준/백준

[백준][Python][15989][DP] 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

DP 문제인데 좀 까다롭다. 

 

1,2,3 더하기 시리즈를 보면 하나같이 DP 문제인데, 이문제가 제일 어려웠다.

 

1,2,3을 써서 숫자를 만드는데, 숫자는 같으면서 순서만 다른건 하나로 하는 것이다.

밑에는 기본적으로 손으로 계산할만한 초기값이다

  1. 1 만들기 ->1
  2. 2 만들기 -> 1+1, 2
  3. 3 만들기 -> 1+1+1, 2+1, 3

그럼 4 만들기는 어떻게 할까?

생각해보면, 1,2,3 쓰는 갯수는 무한이므로 다음과 같이 생각해 볼 수 있다.

 

  • 3 + (1 만드는 갯수)
  • 2 + (2 만드는 갯수)
  • 1 + (3 만드는 갯수)

이렇게 하면 된다. 숫자 쓴것은 같고 순서만 다른건 1개로 하기 때문에 밑의 방식이 가능하다.

 

그럼 5는?

 

  • 4 + (1 만드는 갯수)
  • 3 + (2 만드는 갯수)
  • 2 + (3 만드는 갯수)

 

 

6,7,8...n 을 생각해 보면 다음과 같다.

 

n을 만드는 갯수 : 

 

  • n-1 + (1 만드는 갯수)
  • n-2 + (2 만드는 갯수)
  • n-3 + (3 만드는 갯수)

따라서, DP 배열을 만드는데 DP[만들려는 숫자][1,2,3] 을 만들면 되지 않을까? 해서 만든 코드이다.

 

import sys
n = int(input())

for _ in range(n):

    dp = [[1,0,0],[1,1,0],[1,1,1]]

    a = int(input())
    if a<=3:
        print(sum(dp[a-1]))
        continue
    for i in range(3, a+1):
        tmp = []
        tmp.append(dp[i-1][0])
        tmp.append(dp[i-2][0]+dp[i-2][1])
        tmp.append(dp[i-3][2]+dp[i-3][1]+dp[i-3][0])

        dp.append(tmp)

    print(sum(dp[a-1]))