[실버 3] [Java] 백준 9095번: 1, 2, 3 더하기

아이디어

이 문제도 DP로 푸는거긴 한데, 점화식이 도저히 생각이 안났다. 나는 이거 고등학생때도 조합으로 풀엇다고...

그래서 우선 계산량이 많을 팩토리얼의 값을 선언해두고, 이를 단순 조합식을 사용해서 조합을 계산하고

이중 반복문을 써서 3의 개수, 2의 개수에 따라 총 가능한 경우의 수를 구했다.

 

이를 코드로 구현하면 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class N9095 {
    static int[] factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800};

    public static int findMethod (int n) {
        int count = 0;

        for (int i = n/3; i >= 0; i--) {
            for (int j = (n - 3*i)/2; j >= 0; j--) {
                int ones = n - 3*i - 2*j;
                int length = i + j + ones;
                count += combination(length, i) * combination(length - i, j);
            }
        }
        return count;
    }

    public static int combination (int n, int k) {
        return factorials[n]/(factorials[k] * factorials[n-k]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(findMethod(n));
        }
    }
}

 

그런데 이게 점화식이 있더라. 

우선 n이 1일 때, 가능한 경우의 수는 1개

n이 2일 때, 가능한 경우의 수는 1+1, 2 총 2개

n이 3일 때, 가능한 경우의 수는 1+1+1, 2+1, 1+2, 3 총 4개이다.

이러면 n이 4부터는 마지막에 오는 수가 1인지, 2인지, 3인지에 따라 달라지는데

마지막이 1인 경우는 (n = 3) + 1이므로 n이 3일 때의 경우의 수와 같고

마지막이 2인 경우에는 (n = 2) +1이므로 n이 2일 때의 경우의 수와 같고

마지막이 3인 경우에는 (n = 1) + 3이므로 n이 1일 때의 경우의 수와 같다.

 

같은 원리로 n이 7이라면

마지막이 1인 경우는 (n = 6) + 1이므로 n이 6일 때의 경우의 수와 같고

마지막이 2인 경우에는 (n = 5) +1이므로 n이 5일 때의 경우의 수와 같고

마지막이 3인 경우에는 (n = 4) + 3이므로 n이 4일 때의 경우의 수와 같다.

 

그래서 점화식이 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이라고 한다...

이런 생각을 어떻게 하지? 점화식이 전혀 생각이 안났다...

많이 풀어봐야겠다. 앞 숫자의 결과를 다시 쓸 수 있는 형태인지를 먼저 확인해보는 연습을 해야겠다.

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.