https://www.acmicpc.net/problem/15990
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
1, 2, 3 더하기 4 문제를 푼 다음이어서 그런지 점화식을 빠르게 찾았습니다.
이 문제는 식이 1로 끝나는 경우, 2로 끝나는 경우, 3으로 끝나는 경우로 나누어 해결합니다.
1 → 1
2 → 2
3 → 2+1, 1+2, 3
이제 점화식을 세워보면,
dp[0][N] (N을 나타내는 방법 중 1로 끝나는 방법의 수)
= dp[1][N - 1] + dp[2][N - 1] (N - 1에서 2로 끝나는 방법 + 3으로 끝나는 방법)
dp[1][N] (N을 나타내는 방법 중 2로 끝나는 방법의 수)
= dp[0][N - 2] + dp[2][N - 2] (N - 2에서 1로 끝나는 방법 + 3으로 끝나는 방법)
dp[2][N] (N을 나타내는 방법 중 3로 끝나는 방법의 수)
= dp[0][N - 3] + dp[1][N - 3] (N - 3에서 1로 끝나는 방법 + 2로 끝나는 방법)
이렇게 되겠습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> #define MOD 1000000009 using namespace std; int dp[3][100001]; void init() { dp[0][1] = 1; dp[1][2] = 1; dp[0][3] = 1; dp[1][3] = 1; dp[2][3] = 1; for (int i = 4; i <= 100000; i++) { dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % MOD; dp[1][i] = (dp[0][i - 2] + dp[2][i - 2]) % MOD; dp[2][i] = (dp[0][i - 3] + dp[1][i - 3]) % MOD; } } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); init(); int tc, N; cin >> tc; while (tc--) { cin >> N; cout << ((dp[0][N] + dp[1][N]) % MOD + dp[2][N]) % MOD << '\n'; } return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 15992 1, 2, 3 더하기 7 (0) | 2021.01.22 |
|---|---|
| boj 15991 1, 2, 3 더하기 6 (0) | 2021.01.22 |
| boj 15989 1, 2, 3 더하기 4 (0) | 2021.01.22 |
| boj 15988 1, 2, 3 더하기 3 (0) | 2021.01.22 |
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |