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

문제

풀이

설명

이전의 1,2,3 더하기문제에서 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j
D[i][1] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 1
D[i][2] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 2
D[i][3] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 1

1,2,3 더하기에서 한 것처럼 D[0]=1로 초기화하면 중복이 발생한다.
D[0][1]=1, d[0][2]=1, d[0][3]=1로 초기화 또한 중복이 발생
따라서, 이 문제는 예외처리를 해야한다.

코드

public class Num15990 {
	
	static final long mod = 1000000009L;
    static final int limit = 100000;
    static long[][] d = new long[limit+1][4];
    
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        for (int i=1; i<=limit; i++) {
            if (i-1 >= 0) {
                d[i][1] = d[i-1][2] + d[i-1][3];
                if (i == 1) {
                    d[i][1] = 1;
                }
            }
            if (i-2 >= 0) {
                d[i][2] = d[i-2][1] + d[i-2][3];
                if (i == 2) {
                    d[i][2] = 1;
                }
            }
            if (i-3 >= 0) {
                d[i][3] = d[i-3][1] + d[i-3][2];
                if (i == 3) {
                    d[i][3] = 1;
                }
            }
            d[i][1] %= mod;
            d[i][2] %= mod;
            d[i][3] %= mod;
        }
        
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3])%mod);
        }
		
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/15990