백준 15988 : 1, 2, 3 더하기 3

문제 링크입니다 https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

'9095번 1, 2, 3 더하기' 문제(https://seokeeee.tistory.com/52)와 거의 비슷한 문제였습니다. 다만 이 문제에서는 입력으로 주어지는 n의 범위가 1,000,000까지였습니다. 하지만 O(n)의 시간 복잡도를 보이는 다이나믹 프로그래밍을 이용해 9095번에서 풀었던 동일한 점화식으로 해결할 수 있었습니다. 점화식에 대한 설명은 위에 9095번 문제 링크에 나와있고 이번 문제 풀이 방법은 주석 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
 
int tc, n;
 
// dp[n] : n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수
// n의 범위가 1,000,000 이라, long long int를 사용해야합니다
long long int dp[1000001];
 
int main(void) {
 
    // 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수는 각각
    // 1은 1개, 2는 2개, 3은 4개 입니다
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
 
    // 4부터는 점화식을 활용하여 모든 수에 대해 구해줍니다
    for (int i = 4; i <= 1000000; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        dp[i] %= 1000000009;
    }
 
    scanf("%d", &tc);
    for (int i = 0; i < tc; i++) {
        scanf("%d", &n);
 
        // 각 테스트케이스마다 원하는 값을 출력합니다
        printf("%lld\n", dp[n]); 
    }
    return 0;
}