[백준 BOJ 15998번] 1, 2, 3 더하기 3 (C / C++ ) [DP, 다이나믹프로그래밍]

15988번: 1, 2, 3 더하기 3 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초(추가 시간 없음)	512 MB	10235	3788	2793	36.062%

백준 1, 2, 3 더하기 3 다이나믹프로그래밍 DP C언어 C++ 알고리즘

문제

정수 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은 양수이며 1,000,000보다 작거나 같다.

 

출력

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

 

예제 입력 1

3
4
7
10

 

예제 출력 1

7
44
274

 

풀이

 규칙을 찾기 위해 n값이 작을 때 방법의 수를 구해봅시다.

각각

1.     1

2.     1+1, 2

3.     1+1+1, 1+2, 2+1, 3

1일 때 1가지, 2일 때 2가지, 3일 때 4가지가 나오고 4는 문제에 적혀있는대로 7가지가 나오므로 따로 구하지 않습니다.

마지막으로 5일 때에는

5. 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2

로 총 13가지가 나오는 것을 알 수 있습니다. 이 것을 테이블로 정리해보면

n	1	2	3	4	5
경우의 수	1	2	4	7	13

와 같이 정리가 되는데, 이 때 점화식을 도출해보면

3 <n일 때

dp[n]=dp[n-1]+dp[n-2]+dp[n-3]

인 점화식이 나오는 것을 알 수 있습니다.

 문제에서는 테스트 케이스를 입력받아서 여러 번 출력을 하기 때문에 n을 입력받을 때마다 계산하지 않고, 미리 dp배열에 계산된 값을 저장한 후에 값을 입력받자마자 출력시키면 됩니다.

10억9를 mod하여야 하는데, dp값들의 합이 21억을 한참 초과할 수도 있으므로 long long으로 선언하여야 됩니다

코드

// 1, 2, 3 더하기 3
// 다이나믹 프로그래밍
#include <iostream>
long long dp[1000001]={0,1,2,4};
int main(){
    int T,n;
    std::cin>>T;
    for(int i=4;i<=1000001;i++)dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000009;
    while(T--){
        std::cin>>n;
        std::cout<<dp[n]<<'\n';
    }
}

 

15988번: 1, 2, 3 더하기 3 (acmicpc.net)

15988번: 1, 2, 3 더하기 3