백준 algorithm
백준 15990 - 1, 2, 3 더하기 5
cosmohoo
2020. 4. 23. 16:29
반응형
=> DP 문제이다.
=> 기존 문제아 달리 이차원 배열로 하여 문제를 해결하여야 한다.
- dp[i][j] : i를 1,2,3의 합으로 나타내는 방법의 수, j : 마지막에 사용한 수
- dp[i][1] : 바로 전에 사용할 수 있는 수는 2,3
- dp[i][2] : 바로 전에 사용할 수 있는 수는 1,3
- dp[i][3] : 바로 전에 사용할 수 있는 수는 1,2
if (n - 1 >= 0) {
dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod;
}
if (n - 2 >= 0) {
dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod;
}
if (n - 3 >= 0) {
dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % mod;
위의 알고리즘을 통해 DP를 진행할 수 있다.
초기화의 경우
dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1; //dp initialization
=> 위와 같은 방법으로 초기화를 해주어야 중복을 피할 수 있다.
<전체 코드>
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[100001][4]={0};
const int mod = 1000000009;
const int Max = 100000;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin>> N;
dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1; //dp initialization
for (int n = 4; n <= Max; n++)
{
if (n - 1 >= 0) {
dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod;
}
if (n - 2 >= 0) {
dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod;
}
if (n - 3 >= 0) {
dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % mod;
}
}
int val;
while(N>0)
{
cin >> val;
cout << (dp[val][1] + dp[val][2] + dp[val][3]) % mod<<'\n';
N--;
}
}
반응형