[BOJ] #DP - 9095번 1,2,3 더하기 (JAVA)

문제 출처 : https://www.acmicpc.net/problem/9095

1 = 1

2 = 1 + 1

   = 2

3 = 1 + 1 + 1

   = 2 + 1

   = 1 + 2

   = 3

으로 나 타 낼 수 있다. 이를 S(1), S(2), S(3) 이라고 할 때

4는 S(3)에 +1을 한 것과 같다. 그리고 S(2)에 +2를 한 것과 같다. 마지막으로 S(1)에 +3을 한 것과 같다.

즉, 4 = S(3) + 1 = 1 + 1 + 1

 = 2 + 1 + 1

 = 1 + 2 + 1

 = 3 + 1

= S(2) + 2 = 1 + 1 + 2

 = 2 + 2 

=  S(1) + 3 = 1 + 3

이를 통해 정수 n을 1, 2, 3 의 합으로 나타내는 방법의 수를 S(n) 이라 할 때, 

S(n) = S(n - 1) + S(n -2) + S(n - 3) 임을 알 수 있다.

점화식이기 때문에 다이나믹 프로그래밍의 Bottom-Up으로 문제를 해결하였다.

아래는 전체 코드이다.

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
	static int[] resultArray = new int[12];
	
    public static void main( String[] args ) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		solution();
		for(int i = 0; i < T; i++){
			int result = resultArray[Integer.parseInt(br.readLine())];
			System.out.println(result);
		}
	}
    
	public static void solution (){
		resultArray[1] = 1;
		resultArray[2] = 2;
		resultArray[3] = 4;

		for(int i = 4; i < resultArray.length; i++){
			resultArray[i] = resultArray[i-1] + resultArray[i-2] + resultArray[i-3];
		}
	}
}