백준 9095번: 1, 2, 3 더하기 [DP] - Java :: 매운코딩
728x90
300x250

www.acmicpc.net/problem/9095

 

9095번: 1, 2, 3 더하기

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

www.acmicpc.net

dp배열에 1,2,3의 합으로 나타내는 방법의 수를 넣어놓고 

꺼내서쓴다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static int[] dp;

	public static void main(String[] args)  {

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int n = sc.nextInt();
			dp = new int[12];

			// dp배열은 n을 1,2,3의 합으로 나타내는 방법의 수 출력
			dp[1] = 1; // 1
			dp[2] = 2; // 1+1 , 2
			dp[3] = 4; // 1+1+1, 1+2, 2+1, 3

			for (int i = 4; i <= n; i++) {
				dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];// +1했을 경우, +2했을 경우, +3했을 경우
			}

			System.out.println(dp[n]);

		}

	}

}
728x90

+ Recent posts