[C++] 백준 15990번 : 1, 2, 3 더하기 5 (S3)

#문제

www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

#풀이 & 학습한 내용

중복이 안 되게 해야 하므로 마지막이 어떤 수인지에 대해 구분을 하여 경우의 수를 저장해주어야 한다. 2차원 배열을 선언하여 마지막에 더해지는 수 1, 2, 3에 대해 그 인덱스에 맞는 곳에 경우의 수를 저장한다. 인덱스를 0부터 해도 되지만 마침 마지막에 더해지는 수가 1 ,2, 3이므로 편하게 인덱스 또한 1,2,3일 때에 해당되도록 해서 헷갈리는 일이 없게 했다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
long long int dp[100002][4];
 
int main(void) {
    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;
    }
 
    int T = 0;
    int n = 0;
    cin >> T;
    while (T--) {
        cin >> n;
        cout << (dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009 << '\n';
    }
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_15990.cpp

HoYoungChun/BOJ_algorithm