[BOJ]15990번: 1, 2, 3 더하기 5(java, c++)

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

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

 

 

방법 1: Top-down

import java.io.*;
import java.util.Scanner;
 
public class Main {
 
    public static final long mod = 1000000009L;
    public static long[][] arrResult;
    
    public static void main(String[] args) {
 
        try {
            Scanner sc = new Scanner(System.in);
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int iMax = 100000;
            arrResult = new long[iMax + 1][4];
            
            calculate(iMax);
            
            int iTotalCase = sc.nextInt();
            while (iTotalCase-- > 0) {
                int temp = sc.nextInt();
                bw.write(((arrResult[temp][1] + arrResult[temp][2] + arrResult[temp][3]) % mod)+"\n");
                bw.flush();
            }
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
        
    public static int calculate(int i) {
 
        if (arrResult[i][1] > 0) {
            return 0;
        }
        
        if (i <= 2) {
 
            arrResult[0][1] = 1;
            arrResult[1][1] = 1;
            arrResult[2][2] = 1;
            
            return 0;
        }
        
        calculate(i - 1); 
        
        arrResult[i][1] = (arrResult[i - 1][2] + arrResult[i - 1][3]) % mod;
        arrResult[i][2] = (arrResult[i - 2][1] + arrResult[i - 2][3]) % mod;
        arrResult[i][3] = (arrResult[i - 3][1] + arrResult[i - 3][2]) % mod;
      
        return 0;
    }
}

 

방법 2: Bottom-up

import java.io.*;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        try {
            Scanner sc = new Scanner(System.in);
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
            int iMax = 100000;
            int iMod = 1000000009;
            
            int[] arrOne = new int[iMax + 1];
            int[] arrTwo = new int[iMax + 1];
            int[] arrThree = new int[iMax + 1];
            int[] result = new int[iMax + 1];
 
            arrOne[0] = 1; 
            arrOne[1] = 1;
            result[1] = 1;
            arrTwo[2] = 1;
            result[2] = 1;
            
            
            for (int i = 3; i <= iMax; i++) {
                
                arrOne[i] = (arrTwo[i - 1] + arrThree[i - 1]) % iMod;
                arrTwo[i] = (arrOne[i - 2] + arrThree[i - 2]) % iMod;
                arrThree[i] = (arrOne[i - 3] + arrTwo[i - 3]) % iMod;
                
                result[i] = ((arrOne[i] + arrTwo[i]) % iMod + arrThree[i]) % iMod;
            }
            
            int iTotalCase = sc.nextInt();
            
            while (iTotalCase-- > 0) {
                bw.write(result[sc.nextInt()]+"\n");
                bw.flush();
            }
            
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
 
using namespace std;
 
const int DIV = 1000000009;
const int MAX = 100000;
int sum[MAX + 1][3 + 1];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    /*
     D[N][i] : N을 1, 2, 3의 합으로 나타내는 방법 중 i로 끝나는 경우의 수
 
     점화식 : S[N]    = D[N][1] + D[N][2] + D[N][3]
                    = D[N - 1][2] + D[N - 1][3]
                    + D[N - 2][1] + D[N - 2][3]
                    + D[N - 3][1] + D[N - 3][2]
    */
    /*
     케이스가 주어질 때마다 값을 구하는 것보다,
     MAX만큼 미리 값을 구하고 케이스대로 출력하는 것이 시간효율적이다.
    */
    sum[1][1] = 1;
    sum[2][2] = 1;
    sum[3][1] = 1;
    sum[3][2] = 1;
    sum[3][3] = 1;
    for (int i = 4; i <= MAX; i++)
    {
        sum[i][1] = (sum[i - 1][2] + sum[i - 1][3]) % DIV;
        sum[i][2] = (sum[i - 2][1] + sum[i - 2][3]) % DIV;
        sum[i][3] = (sum[i - 3][1] + sum[i - 3][2]) % DIV;
    }
 
    int cnt;
    cin >> cnt;
 
    while (cnt--)
    {
        int n;
        cin >> n;
        cout << ((sum[n][1] + sum[n][2]) % DIV + sum[n][3]) % DIV << '\n';
    }
 
    return 0;
}

 

바텀업이 더 효율적인 문제.

 

 

TIP1

타일링 문제와 비슷한 유형이다. 

n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

 

N을 1, 2, 3의 합으로 나타내는 방법의 수를 D[N] 이라 하고,

마지막에 k를 더해주는 방법의 수를 A[N][k] 라 하자.

즉, D[N] = A[N][1] + A[N][2] + A[N][3]  이다.

 

타일링 문제를 떠올리며 식을 써보면 다음과 같다. 

D[N] = D[N - 1] x 1을 더하는 방법

          + D[N - 2] x 2를 더하는 방법

          + D[N - 3] x 3을 더하는 방법

 

그런데 문제에서 같은 수를 두 번 이상 연속해서 쓸 수 없다고 했으므로,

1을 더하는 방법을 계산할때에는 D[N - 1] 이 아니라

D[N - 1] 에서 A[N - 1][1] 을 제외한 방법의 수.

즉,  A[N - 1][2] + A[N - 1][3] 을 가져와야 한다.

그리고 k를 더하는 방법은 그냥 1 이므로 

 

식을 다시 정리하면 다음과 같다.

D[N] = (A[N - 1][2] + A[N - 1][3])

          + (A[N - 2][1] + A[N - 2][3])

          + (A[N - 3][1] + A[N - 3][2])

 

 

TIP2

int 표현 범위의 한계가 약 20억이므로, 2개의 수를 더했다면 % 1000000009  를 연산해주자.