DP - 9095. 1, 2, 3 더하기

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		int[] results = new int[12];
		results[1] = 1;
		results[2] = 2;
		results[3] = 4;
		
		for (int i = 4; i < 11; i++) {
			results[i] = results[i-1] + results[i-2] + results[i-3];
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int testCase = Integer.parseInt(st.nextToken());

		for (int i = 0; i < testCase; i++) {
			st = new StringTokenizer(br.readLine());
			int inputNum = Integer.parseInt(st.nextToken());
			System.out.println(results[inputNum]);
		}
	}
}

 

 

설명

result[n]은 result[n-1] + result[n-2] + result[n-3]의 값입니다.

왜냐구요? 한번 생각해보세요

 

1을 1,2,3으로 표현해보면 (1) 밖에 없습니다.

2를 1,2,3으로 표현해보면  (1 + 1)과 (2)의 케이스 밖에 없죠.

(1 + 1) 케이스는 2-1인 모든 케이스인(1)에 1을 더한 케이스에요.

3을 1,2,3으로 표현해보면, (1+1+1), (2+1), (2+1) 케이스가 있어요.

(1+1+1), (2+1)는 3-1의 모든 케이스인 (1+1)과 (2)에 1을 더한 케이스고

(2+1)는 3-2의 모든 케이스인 (1)에 2를 더한 케이스에요

4를 1,2,3으로 표현해보면, (1+1+1+1), (1+2+1), (2+1+1), (3+1), (1+1+2), (2+2), (1+3) 케이스가 있어요.

(1+1+1+1), (1+2+1), (2+1+1), (3+1)는 4-1의 모든 케이스인 (1+1+1)과 (1+2), (2+1), (3)에 1을 더한 케이스고

(1+1+2), (2+2)는 4-2의 모든 케이스인 (1+1), (2)에 2를 더한 케이스에요

(1+3)는 4-3의 모든 케이스인 (1)에 3을 더한 케이스에요.

즉 다시 말해서, k값일 때

마지막 연산이 +1인 녀석들은 result[k-1]에서 그대로 넘어온 녀석들이고,

마지막 연산이 +2인 녀석들은 result[k-2]에서,

마지막 연산이 +3인 녀석들은 result[k-3]에서 넘어왔습니다.

결과적으로 result[n]은 result[n-1] + result[n-2] + result[n-3]의 값입니다.

 

회고

점점 재미있어지고 있습니다~ 화이팅