백준-15990번/1, 2, 3 더하기 5 (java)

 

전에 풀었던 1,2,3 더하기는 연속된 숫자를 허용했지만 이번 문제에서는 연속된 숫자를 사용하지 못한다는게 어려웠다.

 

4가 입력 되었을때의 경우의 수

 

1+(2,3으로 시작되는 합이 3인 경우)

2+(1,3으로 시작되는 합이 2인 경우)

3+(1,2으로 시작되는 합이 1인 경우)

이렇게 하면 연속되는 수가 없이 합의 경우의 수를 구할 수 있다.

 

이런 식으로 점화식을 만들려면 이차원 배열을 이용해야 한다

for(int i=4; i<=100000; i++) {
			arr[i][0]=(arr[i-1][1]+arr[i-1][2])%1000000009;//1+3
			arr[i][1]=(arr[i-2][0]+arr[i-2][2])%1000000009;//2+2
			arr[i][2]=(arr[i-3][0]+arr[i-3][1])%1000000009;//3+1
		}

 

처음에 int형 배열로 했는데 경우의 수가 너무 많아서 오버플로우가 발생했다 그래서 long형 배열로 변경함!

 

<전체 코드>

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		long [][] arr = new long[100001][3];
		arr[1][0]=1;
		arr[2][1]=1;
		arr[3][0]=1;
		arr[3][1]=1;
		arr[3][2]=1;
		
		for(int i=4; i<=100000; i++) {
			arr[i][0]=(arr[i-1][1]+arr[i-1][2])%1000000009;//1+3
			arr[i][1]=(arr[i-2][0]+arr[i-2][2])%1000000009;//2+2
			arr[i][2]=(arr[i-3][0]+arr[i-3][1])%1000000009;//3+1
		}
		
		for(int i=0; i<n; i++) {
			int x=scanner.nextInt();
			System.out.println((arr[x][0]+arr[x][1]+arr[x][2])%1000000009);
		}
	}
}