[백준 15989] 1,2,3 더하기 4 -JAVA // le_effort//

 

이해하는데 정말 오래 걸렸다.... 한 시간 반은 걸린 거 같다....

 

문제에서 주어진 것 처럼 중복을 없애야 한다.

 

일단 dp를 2차원 배열로 설정한다.    - POINT A

dp[n][1]  정수 n을 표현한 수 중 1로 끝나는 것

dp [n][2]  정수 n을 표현한 수 중 2로 끝나는 것

dp [n][3] 정수 n을 표현한 수 중 3으로 끝나는 것

 

중복을 제거하기 위해서는 어떻게 해야 할 까?

2+1+1   , 1+1+2  ,   1+2+1  -> 이 3개는 중복이다.

 

애초에 설정할 때 저 3가지의 숫자 중 하나만 들어가게 하면 되는 게 우리의 목표다.

 

이걸 위해서는 생각해야 할 게 있다.

 

수는 오름차순으로만 있어야 한다

이런 중복의 제거 유형은 대체로 오름차순으로 두어야 한다고 한다.

 

A- 2+1+1  오름차순이 아니다 

B- 1+1+2  오름차순이다

C- 1+2+1  오름차순이 아니다.

 

이것과 POINT-A를 합치면 된다.

 

예를 들어서

dp [4][1]에 들어갈 수 있으려면 3가지를 만족해야 한다.

조건 1. 수들의 합이 4가 되는가?

조건 2. 그렇다면 오름차순으로 되어있는가?

조건 3. 수의 마지막이 1로 끝나는가?

 

일단 POINT-A에 해당하는 조건만 살펴보겠다 

dp [4][1]에서 뒷자리가 1로 끝나는 것 (문제 사진을 참고하길 바란다)

1+1+1+1

2+1+1

1+2+1

3+1

 

일단 이 4개의 숫자는 조건 1과 조건 3을 만족한다.

 

하지만 2+1+1과  1+2+1은 오름차순이 아니므로 배제한다.

 

이제 dp [4][2]를 살펴보자

1+1+2 

2+2 

이렇게 두 가지가 있다 이 두 가지는 3가지 조건을 모두 다 만족한다

 

여기서 1+1+2는   2+1+1 이랑 1+2+1 이랑 중복되는 걸 알 수 있다.

위의 3가지 조건을 다 만족시키면서 중복을 제거할 수 있는 것이다.

 

자 그럼 점화식은 어떻게 세울까?

일단 dp [n][1]을 생각해 보자

마지막 숫자가 1 이어야 한다면 어떤 숫자를 더해야 할까? 당연히 1이다 

 

n이 4일 경우 3에다가 1을 더해야 4가 된다  (조건 1 성립)

n이 4일경우 2에다가 1을 더하면 4가 되지 않는다. (조건 1 성립 X)

 

그러므로 dp [n][1] 은 위의 조건을 잘 생각해 보면  마지막 숫자가 1 이어야 하며 그 수열은 오름차순 이어야 한다

dp [n][1] = dp [n-1][1] 밖에 안된다.

 

n을 4로 예시 들 경우

마지막 숫자가 1로 오려면 dp [3][1], dp [3][2], dp [3][3] 에다가  1을 더해주면 숫자가 4가 완성이 된다.

하지만 dp [3][2]는 마지막 숫자가 2  dp [3][3] 은 마지막 숫자가 3이다

여기다가 1을 더해주면 오름차순이 아니게 된다. 

그러므로 dp [n][1] = dp [n-1][1] 이 되는 것이다

 

마찬가지로 dp [n][2]는 마지막 숫자가 2이어야 하며  n에다가 마지막 숫자 2를 더한 값이 n이 되려면(조건 1)

dp [n-2]를 활용해야 한다.

 

거기다 오름차순 이려면

dp[n][2] = dp[n-2][1] + dp[n-2][2]   

 

dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3] 

 

전체 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,t;
    static StringBuilder sb = new StringBuilder();
    static int dp[][] = new int[10001][4];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        dp[1][1]=1;
        dp[1][2]=0;
        dp[1][3]=0;
        
        dp[2][1]=1;
        dp[2][2]=1;
        dp[2][3]=0;
        
        dp[3][1]=1;
        dp[3][2]=1;
        dp[3][3]=1;
        
        for(int i=4; i<=10000; i++) {
            dp[i][1] = dp[i-1][1];
            dp[i][2] = dp[i-2][1]+dp[i-2][2];
            dp[i][3] = dp[i-3][1]+dp[i-3][2]+dp[i-3][3];
        }
        
        t = Integer.parseInt(br.readLine());
        
        while(t-- >0) {
            n= Integer.parseInt(br.readLine());
            int sum = dp[n][1]+dp[n][2]+dp[n][3];
            sb.append(sum+"\n");
        }
        System.out.println(sb);
    }
}