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

https://www.acmicpc.net/problem/9095

---

풀이

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int[] arr = new int[12];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            int answerIdx = Integer.parseInt(br.readLine());
            for(int j = 4; j <= answerIdx; j++){
                if(arr[answerIdx] == 0) arr[j] = arr[j-3] + arr[j-2] + arr[j-1];
            }

            System.out.println(arr[answerIdx]);
        }
    }
}

 

분할 개념을 생각해보면 생각보다 단순한 점화식이었다.

 

다만 dp라는 것을 모르고 들어왔다면 좀 고생하지않았을까 하는 문제랄까..

 

문제를 볼 때 다양한 알고리즘을 접목시켜보면서 찬찬히 살펴보는 연습을 해야할 필요성을 느꼈다.

 

4를 만드는 방법은 1이라는 숫자에 +3을 하거나, 2 + 2, 3 + 1을 하는 방법이 있다.

그렇기 때문에 위와 같은 점화식이 나오는 것이다.

여기서 단순하게 +3, +2, +1 씩을 붙이니까 이 전의 세개를 더하면 되겠다!라고 느낄 수도 있지만 실수할 수 있는 포인트가 있다.

예를 들면 4를 만들 때 1을 만드는 경우에 수에 +3을 하면 되니까 1의 경우의 수를 더하는건 알겠는데.... 왜 +3을 앞에 해서 1의 경우의 수를 두번 카운트하는건 안 돼? 라는 질문이다.

+3을 한다는 것을 +2 +1, +1 +1 +1로 뜯어서 보면 이 두개는 완전히 동일한 경우의 수이므로 작용되지않는다.