백준 15990 - 1, 2, 3 더하기 5

깃허브:

github.com/MSIQOC/BOJ/blob/master/b15990_123%EB%8D%94%ED%95%98%EA%B8%B05.java

 

www.acmicpc.net/problem/15990

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

참고:

msiqoc.tistory.com/10

백준 9095 - 1, 2, 3 더하기

이전에 1, 2, 3 더하기를 참고하면 더 좋은 문제이다. 이 문제는 1, 2, 3 더하기의 응용문제로, 기존 1, 2, 3 더하기 문제에서는 숫자가 연속되는 것을 허용한다면 이번엔 허용하지 않는 문제이다.

 

같은 수를 두 번 이상 연속해서 사용하면 안된다는 조건이 있기 때문에, 마지막 숫자가 무엇인지에 따라 다음에 들어갈 숫자가 정해지게 된다. 그렇기 때문에, 숫자 x에 관해서 D[x][1], D[x][2], D[x][3]으로 나뉠 수 있고, 각각은 x를 1, 2, 3의 덧셈으로 표현하는 방법 중 1로 끝나는 경우의 수, 2로 끝나는 경우의 수, 3으로 끝나는 경우의 수가 된다. 

 

1부터 3까지 경우의 수 D[1], D[2], D[3]이 다 정해져있다고 했을 때, 4를 만들 수 있는 방법은 다음과 같다:

1) 1을 구하는 방법들 중 1로 끝나거나 2로 끝나면 끝에 3을 더한다. => D[4][3] = D[1][1] + D[1][2] (단, 1을 구하는 방법은 1밖에 없기 때문에 D[1][2]은 0이 된다.)

2) 2를 구하는 방법들 중 1로 끝나거나 3으로 끝나면 끝에 2를 더한다. => D[4][2] = D[2][1] + D[2][3] (단, 2를 구하는 방법은 2밖에 없기 때문에 D[2][1]은 0이 된다.)

3) 3을 구하는 방법들 중 2로 끝나거나 3으로 끝나면 끝에 1을 더한다. => D[4][3] = D[3][2] + D[3][3]

 

따라서 4를 만들 수 있는 경우의 수는 D[4][1] + D[4][2] + D[4][3]이 된다.

 

단, 여기에서 주의해야할 점이 n을 1, 2, 3의 합으로 나타내는 방법의 수를 1000000009로 나눈 나머지를 출력해야한다는 점인데, 이는 나머지 연산을 통해서 쉽게 해결할 수 있다.

나머지 연산

나머지 연산을 사용해서 div가 1000000009라고 했을 때 점화식을 위와 같이 세울 수 있다. n은 100000보다 작거나 같기 때문에 D[1][1]부터 D[3][3]까지 미리 구해둔 다음에 4부터 100000까지는 해당 점화식을 이용해서 구하면 된다.

import java.io.*;
import java.util.*;
public class b15990_123더하기5 {
    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[][] D = new long[100001][4];
        long div = 1000000009;
        D[1][1] = 1;
        D[2][2] = 1;
        D[3][1] = 1;
        D[3][2] = 1;
        D[3][3] = 1;
        for(int i=4; i<=100000; ++i) {
            D[i][3] = (D[i-3][1]%div + D[i-3][2]%div)%div;
            D[i][2] = (D[i-2][1]%div + D[i-2][3]%div)%div;
            D[i][1] = (D[i-1][2]%div + D[i-1][3]%div)%div;
            
        }
        while(t-->0) {
            int n = Integer.parseInt(br.readLine());
            bw.write((D[n][1]%div + D[n][2]%div + D[n][3]%div)%div + "\n");
        }
        bw.flush();
    }
}