[JAVA] 백준 9095번 【1, 2, 3 더하기】

---

위와 같은 원리를 파악하면 쉽다.

 

4 = 3 +1 로 표현할 수 있고, 3을 표현하는 경우의 수는 이미 알고있다.

4 = 2 + 2 로 표현할 수 있고, 2를 표현하는 경우의 수는 이미 알고있다.

4= 1 + 3 로 표현할 수 있고, 1을 표현하는 경우의 수 역시 알고 있다.

 

즉, 

n일 때

n=(n-1) +1

n =(n-2) +2

n =(n-3) +3 로 표현할 수 있고

n을 표현하는 경우의 수는 n-1을 표현하는 경우의 수 + n-2을 표현하는 경우의 수 + n-3을 표현하는 경우의 수 임을 알 수 있다.

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		int[] Dp = new int[10]; // 입력되는 n이 11 미만의 양수이므로

		for (int i = 1; i <= T; i++) {
			int n = scanner.nextInt();
			Dp[0] = 1; // 정수 1 경우의 수
			Dp[1] = 2; // 정수 2 경우의 수
			Dp[2] = 4; // 정수 3 경우의 수
			for (int j = 3; j < 10; j++) {
				Dp[j] = Dp[j - 1] + Dp[j - 2] + Dp[j - 3];
			}
			System.out.println(Dp[n-1]);
		}
	}
}