[BJ/Dynamic] No.9095 - 1, 2, 3더하기

*사고회로 기록용, 무조건 맞는 말 아님.

 

 

 

 

(1). 다이나믹이잖아

애초에 분류를 다이나믹으로 선택했으니, 점화식같은 게 있는지 봐야한다고 생각했음

 

 

(2). 초기 몇개의 합의 개수를 생각해보자

	표시	개수
1	X	0
2	1+1	1
3	1+1+1, 1+2, 2+1	3
4	1+3, 1+1+2, 1+1+1+1, 1+2+1, 2+1+1, 2+2, 3+1	7
5	1+1+3, 1+1+1+2, 1+2+2, 2+1+2, 1+3+1, 1+1+2+1, 1+2+1+1, 2+1+1+1, 2+2+1, 3+1+1	10
6	생략

다 푼 상태에서 생각해보면 이때 함정은 1,2,3의 개수를 연관지어 생각하는 거였다 (문제를 해맨 원인)

1,2,3의 합으로 나타내는 방법이 이 문제의 조건이고,  그에 따라 4부터 일정한 패턴이 주어지는 것을 알아채야한다

 

(3) 7부터 시작되는 패턴

* 7일 때의 표시 = (6의 표시 각각에 +1) or (5의 표시 각각에 +2) or (4의 표시 각각에 +1)

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

 

(4) 이를 4일 때부터 적용하려면,

dp[1] =1, dp[2] = 2, dp[3] =4

로 생각해야한다. '실제 합의 표시개수' 는 아니지만, '1', '2', '3' 자체의 표시가 n=4일 때 부터 적용되므로, 이를 고려하면 내가 사용할 dp 배열은 저렇게 초기설정해야한다 ( 검사할 때는 n=1,2,3 에 대한 별도의 값을 출력하도록 해야겠지. 근데 문제에는 1,2,3이 테스트 안 되는 것 같더라.)

 

 

그래서 dp를 재귀함수로 작성한 코드는 다음과 같다

import java.io.*;

public class baek9095 {
    static int dp [] = new int [11];
    public static void main(String [] args) throws IOException{
        dp[1] = 1;// 1, 실제론 0개
        dp[2] = 2; // 2= 1+1, 실제론 1개
        dp[3] = 4; // 3= 1+1+1= 1+2= 2+1, 실제론 3개

        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));    
        int T = Integer.parseInt(br.readLine());
        int [] answer = new int [T];

        // 케이스마다 입력될 n에 대한 개수를 구하는 함수를 호출한다
        for (int i =0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            answer[i] = recursive(n);
        }

        for(int i =0; i<T; i++){
            System.out.print(answer[i]+"\n");
        }
    }

    // T케이스가 크다고 생각하면...... 어? 생각해도 그냥 저장해야겠네. 어차피 문제에선 11이니까 이게 제일 낫다.
    static int recursive(int n){
        //만약 넘어온 n값이 이미 카운트 된 값이라면, 바로 출력하도록 하자
        if(dp[n] != 0){
            return dp[n];
        }
        // 4부터 시작하여 n까지 점화식으로 구한다
        for(int i=4; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
}