[백준알고리즘] 브루트포스 - 9095번 1,2,3 더하기 문제

https://seul2ya.tistory.com/49

[백준알고리즘] 브루트포스 - 1748번 수 이어쓰기 문제

점화식을 이용해서 푸는 문젠가??

안 어려워 보이는데 막상 풀려니 깔끔한 해결방법이 안떠오른다

흠..뭔가 이전의 정보를 이용해서 다음 값도 구해나가는 식인 것 같으면서도

어떻게 해야 할지 모르겠다

재귀를 이용해야 하는 것 같기도..나 재귀로 푸는법 잘 모르는데

강의를 봐도 제대로 푸는 법은 다음에 설명하겠다고 넘어가서

일단 나도 보류해볼까..하다가 그냥 풀기로 한다

블로그 설명을 보고 나니 아 왜 이걸 생각을 못했지...!!!아쉬웠다

 

우선 1,2,3에서의 경우의 수들은 이렇게 된다

1: 1

(1은 1뿐이다, 총 1개)

2: 1+1, 2

(1의 경우의수 총 1에서 +1을 한 경우 1개, 2 자기 자신 하나, 총 2개)

3: 1+1+1, 2+1, 1+2, 3

1(의 경우의수 총 1개에서 +2를 한 경우 1개, 2의 경우의수 총 2개에서 +1을 한 경우 2개, 3 자기 자신 하나 총 4개)

 

앞의 1,2,3의 경우들을 토대로 4의 경우를 생각해보자

4는 1+3, 2+2, 3+1

즉 1의 경우 나타낼 수 있는 경우의 수는 1개였고 여기서 +3하여 만들 수 있는 4의 경우 또한 1이 되고

2의 경우 나타낼 수 있는 경우의 수는 2개였고 여기서 각각 +2하여 만들 수 있는 4의 경우 또한 2가 되고

3의 경우도 마찬가지로 각각 +1해서 4가지로 표현할 수 있다

그렇게 총 7개!

이전의 경우들을 더하면 구해지는것이다!!

 

5의 예시도 한번 살펴보자

1에서 4를 더하면 5가 되겠지만 1,2,3 숫자들로만 구성해야 하므로 1의 경우는 고려하지 않는다

2의 경우 2개, 3의 경우 4개, 4의 경우 7개

그렇게 총 13개!

2의 경우의수~4의 경우의수들을 모두 합한 개수가 된다

점화식으로 표현하면 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

n-3만큼의 위치에서부터 n까지 해서 최대 세개를 보면 된다(1,2,3중 3이 젤 큰 수이므로)

이제 이를 코드로 구현해보자

 

package baekjoonWeek3;

import java.io.*;
import java.util.StringTokenizer;

public class Plus123 {  //백준 9095번 1 2 3 더하기 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int[] dp = new int[11]; //인덱스 0은 안쓸거임
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4;
        int result;
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());    //n은 0~10
            if (n > 3) {
                for (int j = 4; j <= n; j++) {
                    dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
                }
            }
            bw.write(Integer.toString(dp[n]));
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }
}