728x90
반응형
1. 문제
https://www.acmicpc.net/problem/15988
2. 풀이과정
n의 범위가 (1<=n<=1000000)이므로 n을 1, 2, 3의 합으로 나타내는 방법의 수를
모두 구해보며 개수를 세는 방법은 시간초과가 발생한다.
점화식을 이용하여 다이나믹 프로그래밍으로 풀면된다.
dp[n] : n을 1, 2, 3의 합으로 나타내는 방법의 수
- 1을 1, 2, 3의 합으로 나타내는 방법들
1
=> dp[1] = 1
- 2를 1, 2, 3의 합으로 나타내는 방법들
1 + 1
2
=> dp[2] = 2
- 3을 1, 2, 3의 합으로 나타내는 방법들
1 + 1 + 1
1 + 2
2 + 1
3
=> dp[3] = 4;
- 4를 1, 2, 3의 합으로 나타내는 방법들
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
=> dp[4] = 7;
1+1+1+1, 1+2+1, 2+1+1, 3+1 이 식들은 3을 1, 2, 3의 합으로 나타내는 방법들에 1을 더해준 것이다.
1+1+2, 2+2 이 식들은 2를 1, 2, 3의 합으로 나타내는 방법들에 2을 더해준 것이다.
1+3 이 식은 1을 1, 2, 3의 합으로 나타내는 방법에 3을 더해준 것이다.
따라서 dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7이다.
확장해보면 dp[k] = dp[k-1] + dp[k-2] + dp[k-3] (k>=4)로 나타낼 수 있다.
[코드설명]
위의 설명을 그대로 구현한 코드이다.
3.코드
#include <iostream>
using namespace std;
long long int dp[1000002];
int t;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i=4; i<=1000000; i++) {
long long int sum = 0;
for(int j=i-1; j>=i-3; j--) sum += (dp[j]%1000000009);
dp[i] = sum;
}
cin >> t;
for(int i=0; i<t; i++) {
int num;
cin >> num;
cout << (dp[num]%1000000009) << "\n";
}
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 1780] 종이의 개수 [C++] (0) | 2021.03.15 |
---|---|
[백준 - 1051] 숫자 정사각형 [C++] (0) | 2021.03.14 |
[백준 - 12101] 1, 2, 3 더하기 2 [C++] (1) | 2021.03.14 |
[백준 - 14500] 테트로미노 [C++] (0) | 2021.03.06 |
[백준 - 14501] 퇴사 [C++] (0) | 2021.02.14 |