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

앞서 풀었던 1, 2, 3 더하기의 응용 문제이다.

포인트는

1. 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

2. 1,000,000,009로 나눈 나머지를 출력한다.

 

1번은 2차원 배열을 선언해서 해결

arr[1][n] 는 n을 1, 2, 3의 합으로 나타내는 방법의 수 중 1로 끝난 방법의 수 이다.

고뢰 n+1의 경우의 수를 구할 때 는 

arr[1][n+1] = arr[2][n-1] + arr[3][n-1]

arr[2][n+1] = arr[1][n-2] + arr[3][n-2]

arr[3][n+1] = arr[1][n-3] + arr[2][n-3]

를 구하고

3개의 합 % 1,000,000,009를 하면 된다.

 

2번은 제출 후 틀렷습니다가 나오길래 대체 왜 하다가

찾아보니 int의 MAX_VALUE는 2,147,483,647

계산 중 초과하는 경우가 발생할 수 있어 long으로 타입을 변경해서 선언했다.

 

import java.io.*;

public class Main {
    static final int MAX = 100001;
    static final int DIVISION = 1000000009;
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(reader.readLine());
        long[][] resultArr = new long[4][MAX];

        resultArr[1][1] = resultArr[2][2] = resultArr[3][3] = 1;

        for(int i = 3; i < MAX; i++){
            resultArr[1][i] = (resultArr[2][i-1] + resultArr[3][i-1]) % DIVISION;
            resultArr[2][i] = (resultArr[1][i-2] + resultArr[3][i-2]) % DIVISION;
            if(i > 3) resultArr[3][i] = (resultArr[1][i-3] + resultArr[2][i-3]) % DIVISION;
        }
        while(cnt > 0){
            int input = Integer.parseInt(reader.readLine());
            System.out.println((resultArr[1][input]+resultArr[2][input] + resultArr[3][input]) % DIVISION);
            cnt--;
        }
        reader.close();
    }
}