백준_1, 2, 3 더하기 5_15990

백준_1, 2, 3 더하기 5_15990

https://www.acmicpc.net/problem/15990

문제

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

어떻게 풀었는가

조건

• 테스트 케이스의 개수 T
• 정수 n은 양수이며 100,000보다 작거나 같다.
• n을 1,2,3합으로 나타내는 방법의 수를 1000000009로 나눈 나머지를 출력한다.
  1,2,3만 사용해서 특정 수를 만들어야 한다. 이때 수가 연속되는 경우는 제외해야 한다.

완전 탐색하면 시간 초과가 발생한다.

그러므로 메모이제이션을 사용해서 값을 개수를 구해야한다.

1. 2차원 배열 num은 만들어지는 경우의 수를 저장한다.
   • num[i][1]은 어떤 수에 1를 더해 i를 만드는 경우를 저장한다.
   • num[i][2]은 어떤 수에 2를 더해 i를 만드는 경우를 저장한다.
   • num[i][3]은 어떤 수에 3를 더해 i를 만드는 경우를 저장한다.
2. 1,2,3의 경우는 정해저 있기 때문에 미리 num에 해당하는 값을 저장한다.
3. for을 사용하여 4부터 100000까지 순회하면서 값을 구한다.
   • 이때 같은 수가 연속되면 안되기 때문에 중복되는 경우를 제외하여 더한다.
4. for을 사용하여 n의 1,2,3 합을 더한 후 1000000009로 나눈 나머지를 출력한다.

코드

#include <iostream>

using namespace std;

int num[100001][4];
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    num[1][1] = 1;
    num[2][2] = 1;
    num[3][1] = 1;
    num[3][2] = 1;
    num[3][3] = 1;

    for (int i = 4; i <= 100000; ++i)
    {
        num[i][1] = (num[i - 1][2] + num[i - 1][3]) % 1000000009;
        num[i][2] = (num[i - 2][1] + num[i - 2][3]) % 1000000009;
        num[i][3] = (num[i - 3][1] + num[i - 3][2]) % 1000000009;
    }
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        long long sum = 0;
        for (int i = 1; i < 4; ++i)
        {
            sum += num[n][i];
        }
        cout << sum % 1000000009 << "\n";
    }
    return 0;
}

결과