[백준] 9095 1, 2, 3 더하기 - 자바(JAVA)

 

• n을 1, 2, 3의 합으로 나타내는 경우의 수
  • 우선 1, 2, 3을 만들 수 있는 경우의 수는
  •  1 은 {1}로 1개
  • 2는 {1+1, 2}로 2개
  • 3은 {1+1+1, 1+2, 2+1, 3}으로 4개

 

• 그렇다면 4는 어떻게 만들 수 있을까?  1, 2, 3의 각 경우의 수에 +3, +2, +1을 하면 4를 만들 수 있다! →{1+3 / 2+2 / 3+1} 
  • 즉,  경우의 수는 1+2+4로 7개

 

• 5도 마찬가지로, 2, 3, 4의 각 경우의 수에 +3, +2, +1을 하면 5를 만들 수 있다! →{2+3 / 3+2/ 4+1}
  • 즉,  경우의 수는 2+4+7로 13개

 

 

→이를 통해 점화식을 유추해보면 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		
		int dp[] = new int [11];
		
		dp[1] =1;
		dp[2]=2;
		dp[3]=4;
		
		for(int j=4;j<=10;j++) { 
			dp[j] = dp[j-3] + dp[j-2] + dp[j-1]; 
		}
		
		
		for(int i=0; i<t; i++) {
			int n=sc.nextInt();
			System.out.println(dp[n]);
		}
			
	}
}

 

• 문제에서 정수 n은 양수이며 11보다 작다고했으므로
  • j는 4부터 10까지만