[JAVA] 백준 알고리즘, 9095번 : 1, 2, 3 더하기 (DP, 다이나믹 프로그래밍)

백준 9095번 DP의 기본 문제 1, 2, 3번 더하기 문제를 풀어봤다.

게임 개발을 해봤으면서 주 언어가 JAVA인 나는 자바로 풀이를 하겠다.

이 문제의 원리는 매우 간단하다.

이 문제는 하나의 자연수를 1, 2, 3 으로만 조합하여 더해서 해당 자연수가 나오는 경우의 수를 구하는 문제이다.

그렇다면 먼저 1, 2, 3의 경우의 수를 찾아 봐야 한다.

d[0]은 0

d[1] = 1밖에 없으니 경우의 수는 1

d[2] = (1 + 1), (2) 즉 경우의 수는 2

d[3] = (1 + 1 + 1), (1 + 2), (2 + 1), (3) 즉 경우의 수는 3

이렇게 되어 있을 때 d[4]는  (1+1+1+1), (1+1+2), (1+2+1),  (2+1+1), (2+2), (1+3), (3+1) 으로 7개가 된다.

이것을 DP로 풀어야 한다.

DP의 가장 큰 특징은 문제를 작은 문제로 쪼갤 수 있어야 한다.

그리고 작은 문제보다 더 작은 문제로부터 답을 알고있어야 한다.

말로 풀면 굉장히 어렵지만, 우리가 지금 알고 있는 경우의 수는 0과 1, 2, 그리고 3뿐이다. 이를 이용해서 문제를 쭉 풀어야 한다.

그렇다면 이 1, 2, 3 세가지 경우로만 생각해서 문제를 풀면 어떻게 될까?

d[4]를 생각할 때

1. 4는 1 + 3 이다. 3을 1, 2, 3 더하기로 하였을 때의 경우의 수는 4가지이다.
2. 4는 2 + 2이다. 2를 1, 2, 3 더하기로 하였을 때의 경우의 수는 2가지이다.
3. 4는 3 + 1이다. 3을 1, 2, 3 더하기로 하였을 때의 경우의 수는 1가지이다.

즉, 4 + 2 + 1을 하면 7가지가 된다.

이렇게 d[5]를 마저 생각하게 되면

1. 5는 1 + 4이다. 4를 1, 2, 3 더하기로 하였을 때의 경우의 수는 7가지이다.
2. 5는 2 + 3이다. 3를 1, 2, 3 더하기로 하였을 때의 경우의 수는 4가지이다.
3. 5는 3 + 2이다. 2을 1, 2, 3 더하기로 하였을 때의 경우의 수는 2가지이다.

즉, 7 + 4 + 2를 하면 d[5]는 13개가 된다.

이렇게 작은 문제로부터 구해진 문제를 자료구조에 저장을 해야 하는데 이것을 Memorization라고 부른다.

이제 문제를 풀어보도록 하자.

방법은 작은 문제부터 풀어가는 bottom-up방식으로 풀었다. 시간이 나면 top-down으로 다시 풀고 싶다.

import java.util.*;

public class Beak_9095 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[] array = new int[11];
		
		array[0] = 0;
		array[1] = 1;
		array[2] = 2;
		array[3] = 4;
		

		int a = 0;
		for(int i = 0; i < num; i++) {
			a = sc.nextInt();
			for(int j = 4; j <= a; j++) {
				array[j] = array[j - 1] + array[j - 2] + array[j - 3];
			}
			System.out.println(array[a]);
		}
	}

}