[JAVA] 백준 (실버2) 15990번 1, 2, 3 더하기 5

AIR·2024년 2월 27일

다이나믹 프로그래밍 백준 실버 코딩테스트

코딩 테스트 문제 풀이

목록 보기

59/135

링크

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

문제 설명

정답률 30.872%
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력 예제

3
4
7
10

출력 예제

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

정답 코드

두 수를 연속해서 더한다는 조건이 없으면 점화식은 $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ 이지만
2+2 이런식으로 두 수를 연속해서 더할 수가 없다.
그래서 마지막으로 더하는 수를 이차원 배열을 이용하여 카운트한다.
가령 dp[3][1]는 더해서 3이 되는 경우 중 1로 끝나는 경우, 즉 2+1이 되고 dp[3][2]는 1+2가 된다.
그렇게 해서 1부터 3까지의 배열을 다음과 같이 구성한다.

dp[1][1] = 1; //1
dp[2][2] = 1; //2
dp[3][1] = 1; //2+1
dp[3][2] = 1; //1+2
dp[3][3] = 1; //3

이제 4를 생각해볼 때
dp[4][1]는 끝에 1을 더해야 하므로 그 전에 합은 3이 되야 하고 1은 오면 안되므로 dp[3][2], dp[3][3]이 올 수 있다.
그렇게 해서 dp[4]의 원소는 다음과 같다.

dp[4][1] = dp[3][2] + dp[3][3];
dp[4][2] = dp[2][1] + dp[2][3];
dp[4][3] = dp[1][1] + dp[1][2];

여기서 일반화하면 다음과 같다.

dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
dp[i][2] = dp[i - 2][1] + dp[i - 2][3];
dp[i][3] = dp[i - 3][1] + dp[i - 3][2];

코드

public class Main {

    private static final int MAX = 100_001;
    static long[][] dp = new long[MAX][4];


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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine()); //테스트 케이스 개수

        dp[1][1] = 1; //1 = 1
        dp[2][2] = 1; //2 = 2
        dp[3][1] = 1; //3 = 2 + 1
        dp[3][2] = 1; //3 = 1 + 2
        dp[3][3] = 1; //3 = 3

        //dp 초기화
        for (int i = 4; i < MAX; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009;
        }

        for (int testCase = 0; testCase < T; testCase++) {
            int n = Integer.parseInt(br.readLine());
            //n번째 원소의 합
            long result = Arrays.stream(dp[n]).sum();
            System.out.println(result % 1000000009);
        }
    }

}