[DP] DP 간단한 문제 백준 1, 2, 3 더하기 풀기

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

 

예제 입력

3
4
7
10

예제 출력

7
44
274

 

풀이 방법

 

먼저 1을 더할때는 구하는 방식이 1 하나밖에 없으므로 dp[0] = 1로 저장합니다.

두번째로 2를 구하는 방식은 1+1 과 2가 있으니 dp[1] = 2를 저장하겠습니다. 

마지막으로 3을 구하는 방식은 1+1+1, 1+2, 2+1, 3 총 4가지가 있으니 dp[2]는 4로 저장하겠습니다.

 

이제 응용하면 4를 구할때 부터는 4는 1+3, 2+2, 3+1가 있는데 여기서 이것을 표현하려고 하면

• 1 + dp[2] : 방법 4가지
• 2 + dp[1] : 방법 2가지
• 3 + dp[0] : 방법 1가지

이것을 모두 더하면 7이 나옵니다. 

 

이제 마지막으로 5를 구하는 방식을 보면서 어떤식으로 흘러가는지 보겠습니다. 

5를 만들기 위해서는 1+4, 2+3, 3+2가 있는데 이것을 표현하면

• 1 + dp[3] : 7가지
• 2 + dp[2] : 4가지
• 3 + dp[1] : 2가지

이것을 모두 더하면 13이 나옵니다. 이것을 통해 점화식을 세우면

 

dp[n] = dp[n-3] + dp[n-2] + dp[n-1]  (n>=3) 인것을 확인할 수 있습니다. 이제 코드를 통해 표현해 보겠습니다.

 

코드 구현

n = int(input())

# print(dp)


def ans(n):
    if n <= 3:
        dp = [1, 2, 4]
        return dp[n-1]
    elif n > 3:
        dp = [1, 2, 4] + [0]*(n-3)
        for i in range(3, n):
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        return dp[-1]


for _ in range(n):
    print(ans(int(input())))

 

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기