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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

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

 

 

 

 

 

 

 

 

 

 

 

 

 dp문제의 점화식을 어떻게 세우는지 감이 잡히게 된 문제였다. 

 

dp문제에서 가장 중요한것은

 

현재상태의 직전상태를 생각해서 점화식을 만든다는것이다.

 

이게 무슨말이냐면  

 

위 문제는 어떤 정수를 1,2,3의 합으로 나타낼수 있는데 이때 나타낼수 있는 방법이 총 몇가지냐를 묻는 문제다. 

 

예를 들어

 

4를 1,2,3의 합으로 나타낸다고 했을때 현재상태의 직전상태를 생각해서 점화식을 만들어보자.

 

현재상태: 4

직전상태: 4에서 1을 뺀 상태(3), 4에서 2를 뺀 상태(2) 4에서 3을 뺀 상태(1) 으로 총 3개이다 

4가 되기 직전에 1을 더했는지 2를 더했는지 3을 더했는지는 모르니 case를 3가지로 나눌수 있다 

 

4=3+1

4=2+2

4=1+3

-> 이게 정확히 무슨 뜻이냐면

 

dp[4]를 4를 1,2,3의 합으로 나타 낼수 있는 모든 경우의수라고 하였을때 

 

dp[4]=dp[3]+dp[2]+dp[1]을 만족한다

1을 더하는지 2를 더하는지 3을 더하는지는 경우의수와 상관없다

이미 case를 3개 나눈거에서 우리는 모든 경우를 다 따진것이다

 

최종적으로

dp[n]=dp[n-1]+dp[n-2]+dp[n-3]이라는 점화식이 나온다

점화식만 나온다면 구현은 수월해 진다  

 

 

 

 

import java.util.*;
public class Main {
    public static  int [] dp=new int[11]; //메모할 저장소
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
            int n=sc.nextInt();
            int answer = DP(n);
            System.out.println(answer);
        }
    }


    public static int DP (int n){
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }

        return dp[n];
    }
}