[백준] 1, 2, 3 더하기 8 (15993번 JAVA)

[백준]  1, 2, 3 더하기 8 (15993번 JAVA)

---

[접근 방법]

 

2차원 배열로 구성해야 한다.

수식에서 숫자가 홀수개로 구성된 것과 짝수개로 구성된 것을 따로 저장해야 한다.

 

정수 n이 짝수개로 구성 : dp[n][0]

정수 n이 홀수개로 구성 : dp[n][1]

 

와 같이 정의 하였다.

 

초기값은 다음과 같이 설정하였다.

	long[][] dp = new long[100_001][2];
        // 정수 n이 짝수개로 구성 : dp[n][0]
        // 정수 n이 홀수개로 구성 : dp[n][1]
        dp[1][1] = 1; // 1
        dp[2][0] = 1; // 1+1
        dp[2][1] = 1; // 2
        dp[3][0] = 2; // 1+2, 2+1
        dp[3][1] = 2; // 1+1+1, 3

 

정수 n이 짝수개로 구성된 경우 (dp[n][0]) 를 찾기 위해선,

n-1, n-2, n-3이 홀수로 구성된 경우의 수식에 각각 +1, +2, +3을 뒤에 이어주기만 하면 된다고 생각했다. 

홀수도 마찬가지의 경우다.

 

따라서 다음과 같은 점화식을 도출하였다.

 

짝수의 경우
dp[i][0] = dp[i-1][1] + dp[i-2][1] + dp[i-3][1]

홀수의 경우
dp[i][1] = dp[i-1][0] + dp[i-2][0] + dp[i-3][0] 

(단, n>= 4)

---

[JAVA  코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        
        long[][] dp = new long[100_001][2];
        // 정수 n이 짝수개로 구성 : dp[n][0]
        // 정수 n이 홀수개로 구성 : dp[n][1]
        dp[1][1] = 1; // 1
        dp[2][0] = 1; // 1+1
        dp[2][1] = 1; // 2
        dp[3][0] = 2; // 1+2, 2+1
        dp[3][1] = 2; // 1+1+1, 3

        for(int i=4; i<=100_000; i++){
            dp[i][0] = (dp[i-1][1] + dp[i-2][1] + dp[i-3][1]) % 1_000_000_009;
            dp[i][1] = (dp[i-1][0] + dp[i-2][0] + dp[i-3][0]) % 1_000_000_009;
        }

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][1] +" "+ dp[n][0] + "\n");
        }

        bw.flush();
        bw.close();
    }
}