백준 9095 문제 (순열을 이용한 풀이 및 dp 풀이) - 자바(JAVA)

https://www.acmicpc.net/problem/9095 < 백준 9095번(1, 2, 3 더하기)

 

먼저 dp에 익숙하지 않았던 나는 백준 9095 문제를 보고 어떻게 접근해야 할지 고민하다

 

7을 예로 들었을 때
1111111   1
2 하나 ->  6개 211111   2311
2 두 개 ->  22111  5! / (2!*3!)
2 3개 -> 2221  4!/3!  4
3 하나 -> 31111 5! / 4!
3 두개 -> 331  3! / 2!
2 하나 + 3 하나 -> 2311 4!/2! -> 12
2 두개 + 3 하나 -> 223   3

이런 식으로 경우의 수를 나눠 순열조합으로 풀 수 있을 거라 생각을 해서
아래와 같이 문제를 풀었다.

 

순열을 이용한 풀이

---

import java.util.*;
public class Bj9095 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] nums = new int[T];

        for (int i = 0; i < T; i++) {
            nums[i] = sc.nextInt();
        }

        countAll(nums);

    }

    static void countAll(int[] nums) {
        for (int num : nums) {
            System.out.println(count(num));
        }
    }

    static int count(int num) {
        int n = 1;
        int result2 = num / 2;
        int result3 = num / 3;

        for (int i = 1; i <= result2; i++) {
            int a = num - i*2;
            n += factorial(num - i) / (factorial(i) * factorial(a));
            if (a > 0) {
                for (int j = 1; j <= a / 3; j++) {
                    n += factorial(num - i - j * 2) / (factorial(i) * factorial(j) * factorial(a - j * 3));
                }
            }
        }
        for (int k = 1; k <= result3; k++) {
            int b = num - k*3;
            n += factorial(num - k * 2) /(factorial(k) * factorial(b));
        }
        return n;
    }

    static int factorial(int num){
        if (num == 0) {
            return 1;
        } else{
            return num * factorial(num - 1);
        }
    }
}

 

먼저 주어지는 값을 2로 나눠 그 몫만큼 for문을 돌려 i값에 따라 순열 값을 추가해 주고

i에 따른 2의 추가 후 남은 1의 값을 다시 3으로 나눠 그 몫만큼 for문을 돌려 j값에 따라 순열 값을 추가해 줬다.

 

그 후에는 남은 경우의 수는 3과 1로만 이루어진 경우밖에 없기 때문에

3으로 나눈 몫만큼 for문을 돌려 n에 순열값을 추가해 주어

답을 구했었다.

 

그런데 아무리 생각해 봐도 이렇게 푸는 건 생각하는 것도 오래 걸리고 실버 3 난이도에 비해 높다고 생각해서

찾아보니 이 문제는 dp를 활용하여 푸는 문제인 걸 알게 됐다

 

아래는 dp를 활용하여 푼 코드이다

 

 

dp를 활용한 풀이

---

 

import java.util.*;
public class Bj9095ver2 {
    static int dp[] = new int [11];
    public static void main(String[] args)   {
        Scanner sc = new Scanner(System.in);


        int t = sc.nextInt();
        dp[1] =1; //초기 값 초기화
        dp[2]=2;
        dp[3]=4;

        for(int j=4;j<=10;j++) { // 4부터 반복
            dp[j] = dp[j-3] + dp[j-2] + dp[j-1]; // 점화식
        }

        for(int i=0;i<t;i++) {
            int n = sc.nextInt();

            System.out.println(dp[n]);
        }
    }

}

 

코드가 훨씬 간결하다!

 

문제의 접근 방식을 알아보면

4를 예시로 들면  4는 {dp [1] +3, dp [2] +2, dp [3] +1}로 구성되어 있기 때문에

dp [4] = dp [1] + dp [2] + dp [3] 이 됩니다.  dp [x] 뒤에 붙는 + n 같은 경우는 경우의 수에 영향을 끼치지 않기 때문입니다.

 

그렇다면

 

dp(n)은,

- dp(n-1), 즉 n-1을 만드는 모든 경우 각각에 대해 그 뒤에 1을 더하는 것과

- dp(n-2), 즉 n-2를 만드는 모든 경우 각각에 대해 그 뒤에 2를 더하는 것과

- dp(n-3), 즉 n-3을 만드는 모든 경우 각각에 대해 그 뒤에 3을 더하는 것으로 구성되어 있기에

 

dp [n] = dp [n-1] + dp [n-2] + dp [n-3]으로 값을 구할 수 있게 됩니다.

 

그렇다면 문제가 만약 1, 2, 3 더하기가 아닌 1,2,3,4 더하기라면 dp [n]의 값은 어떻게 될까요??

 

결론은 dp[n] = dp [n-1] + dp [n-2] + dp [n-3] + dp [n-4]가 되게 됩니다

 

혹시 이해가 잘 안 되시거나 하면 댓글 남겨주세요!