[백준 15990] 1, 2, 3 더하기 5 (자바)

백준 15990번 1, 2, 3 더하기 5 (자바)

 

 

 

출처

www.acmicpc.net/problem/15990

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

 

 

 

문제

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

• 1+2+1
• 1+3
• 3+1

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

 

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

1, 2, 3 더하기 문제에서 수를 연속해서 사용할 수 없다는 조건이 추가되었다.

이 문제는 이차원 배열을 만들어 1,2,3 각 경우의 수를 분리해주어야 한다.

많은 사람들이 숫자가 끝나는 경우로 구별했기 때문에 나도 그렇게 했다.

 

n=1 -> 1 -> 1(1) 2(0) 3(0)

n=2 -> 2 -> 1(0) 2(1) 3(0)

n=3 -> 12 21 3 -> 1(1) 2(1) 3(1)

n=4 -> 121 13 31 -> 1(2) 2(0) 3(1)

...

 

4까지 나열한 위 경우를 보면 규칙을 찾을 수 있다.

1로 끝나는 경우는 n-1 경우에서 자신을 제외한 [n-1][2] + [n-1][3]을 더하면 된다.

(ex) n=4 - 1(2) = 2(1) + 3(1))

2로 끝나는 경우는 n-2경우에서 자신을 제외한 [n-2][1] + [n-2][3]을 더하면 된다.

(ex) n=4 - 2(0) = 1(0) + 3(0))

3으로 끝나는 경우는 n-3경우에서 자신을 제외한 [n-3][1] + [n-3][2]을 더하면 된다.

(ex) n=4 3(1) = 1(1) + 2(0))

 

점화식 : 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]

 

 

 

내 코드

package practice;

import java.util.Scanner;

public class OneTwoThreeSum5 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long[] result = new long[n];
		long[][] dp = new long[1000001][4];
		
		dp[1][1] = 1;
		
		dp[2][2] = 1;
		
		dp[3][1] = 1;
		dp[3][2] = 1;
		dp[3][3] = 1;
		
		int num;
		for (int i=0; i<n; i++) {
			num = sc.nextInt();
			
			if (num > 3) {
				for (int j=4; j<=num; j++) {
					dp[j][1] = (dp[j-1][2] + dp[j-1][3]) % 1000000009;
					dp[j][2] = (dp[j-2][1] + dp[j-2][3]) % 1000000009;
					dp[j][3] = (dp[j-3][1] + dp[j-3][2]) % 1000000009;
				}
			}
			
			result[i] = (dp[num][1] + dp[num][2] + dp[num][3]) % 1000000009;
		}
		
		for (int i=0; i<result.length; i++) {
			System.out.println(result[i]);
		}
		
	}
}

 

 

 

고려할 점

1. 규칙을 찾아 점화식을 세울 것

2. 직접 써보며 규칙을 찾을 것

3. 제한에 따른 범위를 생각할 것

4. 1차원 배열로 해결방법이 안 보인다면 2차원 배열을 사용할 것