코딩스토리

백준 15990번 - 1, 2, 3 더하기 5 본문

알고리즘/BOJ 문제 풀이

백준 15990번 - 1, 2, 3 더하기 5

kimtaehyun98 2020. 11. 24. 12:23

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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll dp[100004][4];
    int t, n;
 
    dp[1][1] = 1; dp[1][2] = 0; dp[1][3] = 0;
    dp[2][1] = 0; dp[2][2] = 1; dp[2][3] = 0;
    dp[3][1] = 1; dp[3][2] = 1; dp[3][3] = 1;
    for (int i = 4; i <= 100000; i++) {
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009;
        dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009;
        dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009;
    }
 
    cin >> t;
    while (t--) {
        cin >> n;
        cout << (dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009 << "\n";
    }
}
 cs

간단한 dp문제였다.

'알고리즘 > BOJ 문제 풀이' 카테고리의 다른 글

백준 2621번 - 카드게임  (0) 2020.12.27
백준 1197번 - 최소 스패닝 트리  (1) 2020.12.17
백준 2150번 - Strongly Connected Component  (0) 2020.11.24
백준 17134번 - 르모앙의 추측  (0) 2020.11.24
백준 15576 - 큰 수 곱셈 (2)  (0) 2020.11.24
'알고리즘/BOJ 문제 풀이' Related Articles more
Comments