반응형
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[dp] - 1,2,3 더하기 5 (15990)
[ 문제 ]
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- 1+2+1
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
[ 입력 ]
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
[ 출력 ]
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
[ 코드 ]
#include<iostream>
using namespace std;
long long d[100001][4];
const long long mod = 1000000009LL;
const int limit = 100000;
// dp[n][i] : 마지막에 오는 수가 i일때, 1,2,3의 합으로 정수 n을 만드는 경우의 수
// 점화식을 이차원 배열로 구성함.
// 조건 ) n>=i
// dp[n][1] = dp[n-1][2] + dp[n-1][3] // 마지막에 오는 숫자가 1일때 경우의 수
// dp[n][2] = dp[n-2][1] + dp[n-2][3] // 마지막에 오는 숫자가 2일때 경우의 수
// dp[n][3] = dp[n-3][1] + dp[n-3][2] // 마지막에 오는 숫자가 3일때 경우의 수
// result = dp[n][1] + dp[n][2] + dp[n][3]
int main() {
for (int i = 1; i <= limit; i++)
{
if (i >= 1)
{
d[i][1] = d[i - 1][2] + d[i - 1][3];
// dp[1][1] : 마지막에 오는 숫자가 1일 때, 1,2,3의 합으로 정수 1을 만드는 경우
if (i == 1)
{
d[i][1] = 1;
// 이들은 경우의 수가 1개씩 밖에 나오지 않음. 또한, n>=i여야 연산이 가능함.
}
}
if (i >= 2)
{
d[i][2] = d[i - 2][1] + d[i - 2][3];
// dp[2][2] : 마지막에 오는 숫자가 2일 때, 1,2,3의 합으로 정수 2를 만드는 경우
if (i == 2)
{
d[i][2] = 1;
// 이들은 경우의 수가 1개씩 밖에 나오지 않음. 또한, n>=i여야 연산이 가능함.
}
}
if (i >= 3)
{
d[i][3] = d[i - 3][1] + d[i - 3][2];
// dp[3][3] : 마지막에 오는 숫자가 3일 때, 1,2,3의 합으로 정수 3을 만드는 경우
if (i == 3)
{
d[i][3] = 1;
// 이들은 경우의 수가 1개씩 밖에 나오지 않음. 또한, n>=i여야 연산이 가능함.
}
}
d[i][1] %= mod;
d[i][2] %= mod;
d[i][3] %= mod;
}
int T; // 테스트 케이스 개수
cin >> T;
while (T--)
{
int n;
cin >> n;
cout << (d[n][1] + d[n][2] + d[n][3]) % mod << '\n';
// while문에서는 출력 때 '\n' 꼭 고려해주기
}
return 0;
}
반응형
'문과 코린이의, [C. C++] 기록 > C++ 백준 문제풀이' 카테고리의 다른 글
[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 일곱 난쟁이 (2309) (0) | 2021.08.08 |
---|---|
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 2 x n 타일링 2 (11727) (0) | 2021.08.01 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[dp] - 스티커 (9465) (0) | 2021.07.31 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 골드바흐 파티션 (17103) (0) | 2021.07.31 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 접미사 배열 (11656) (0) | 2021.07.30 |