[Baekjoon] 백준 15990번 1,2,3더하기 5

15990번 1,2,3더하기5 문제 풀이

문제

• 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
  정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

• 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제

입력
3
4
7
10

출력
3
9
27

코드

1. 시간초과 발생 코드

   #include<iostream>
   using namespace std;
   

long long d[100001][4];
long long mod = 1000000009;
int main() {
int t;
cin >> t;

while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        if (i - 1 >= 0) {
            d[i][1] = d[i - 1][2] + d[i - 1][3];
            if (i == 1) d[i][1] = 1;
        }
        if (i - 2 >= 0) {
            d[i][2] = d[i - 2][1] + d[i - 2][3];
            if (i == 2) d[i][2] = 1;
        }
        if (i - 3 >= 0) {
            d[i][3] = d[i - 3][1] + d[i - 3][2];
            if (i == 3) d[i][3] = 1;
        }
        d[i][1] %= mod;
        d[i][2] %= mod;
        d[i][3] %= mod;
    }
    printf("%lld\n", (d[n][1] + d[n][2] + d[n][3]) % mod);
}

}

2. 시간초과 해결 코드
```c
#include<iostream>
#include<algorithm>
using namespace std;

long long d[100001][4];
long long mod = 1000000009;
int main() {
    for (int i = 1; i <= 100000; i++) {
        if (i - 1 >= 0) {
            d[i][1] = d[i - 1][2] + d[i - 1][3];
            if (i == 1) d[i][1] = 1;
        }
        if (i - 2 >= 0) {
            d[i][2] = d[i - 2][1] + d[i - 2][3];
            if (i == 2) d[i][2] = 1;
        }
        if (i - 3 >= 0) {
            d[i][3] = d[i - 3][1] + d[i - 3][2];
            if (i == 3) d[i][3] = 1;
        }
        d[i][1] %= mod;
        d[i][2] %= mod;
        d[i][3] %= mod;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        printf("%lld\n", (d[n][1] + d[n][2] + d[n][3]) % mod);

    }
}

1. 시간초과 : 배열에 저장되어 있는 값은 변경될 일이 없는데 n값을 새로 입력받을때마다 배열의 값을 다시 구해야한다.
2. 시간초과 해결 : 위와같은 문제를 해결하기 위하여 우리가 입력할 수 있는 n의 최대값을 for문의 두 번째 인자로 넣어 미리 배열을 채워넣도록 한 후 마지막 출력문만 반복할 수 있도록했다.

해결방법

• d[i][j] = i를 1,2,3의 합으로 나타낼 때 마지막에 사용한 숫자는 j이다.
• d[i][1], d[i][2], d[i][3]의 경우의 수를 모두 구하여 더해주면 우리가 원하는 값을 찾을 수 있다.
• n=4인경우 d[4][1] = d[3][2]+ d[3][3], 즉 3을 1,2,3합으로 나타낼 때 마지막에 사용한 숫자가 2와 3인 경우의 수를 합한 것과 같다. 마찬가지로 d[4][2] = d[2][1] + d[2][3], d[4][3] = d[1][1] + d[1][2]로 나타낼 수 있다.
• 쉽게 4를 세가지 수의 합으로 나타낼 때 j=3인경우는 4를 완성시키기 위해 3을 사용한 경우이기 때문에 d[4-3][1] + d[4-3][2]로 경우의 수를 구할 수 있으니 다른 수에 대해서도 똑같은 식을 세워 원하는 답을 구하면 된다.
• 마지막으로 주의할 점으로는 d[1][1], d[2][2] , d[3][3]세 가지의 경우의 수는 항상 1,2,3 본인만 갖게 되니 1로 고정된다. 예외처리를 하기 위해 조건문을 사용하여 계산 후에 1로 덮어씌우는 코드를 작성해주었다.