12996번 - Acka(재귀, dp)

문제:

 

풀이:

일반적인 재귀로 풀기에는 너무 많은 반복이 발생한다.

S의 범위가 크지 않은 것으로 보아 dp를 이용해 풀면 좋을 것 같다.

그렇다면 어떻게 dp를 이용해야 할까? 아래 예시를 통해 알아보도록 하자.

 

입력: 3 2 1 1

각 차례에서 노래를 선택할 수 있는 방법은 아래와 같다.

	인원 1	인원 2	인원 3
1	O	O	O
2	O	O	X
3	O	X	O
4	X	O	O
5	O	X	X
6	X	O	X
7	X	X	O

총 7가지 방법을 선택할 수 있다. 주어진 입력에서 어떤 경우의 수로 앨범을 만들 수 있나 살펴보자.

 

일단 방식 1을 첫번째로 택해봤다.

S	인원1	인원2	인원3
3	2	1	1
2	1	0	0
1	0	0	0
0	X	X	X

방식1을 택하면 앨범이 만들어지지 않는다.

계속해서 2번째 방식을 택해보겠다.

S	인원1	인원2	인원3	인원1	인원2	인원3	인원1	인원2	인원3
3	2	1	1	2	1	1	2	1	1
2	1	0	1	1	0	1	1	0	1
1	0	0	0	0	0	1	1	0	0
0	X	X	X	0	0	0	0	0	0

총 2가지 경우의 수가 나왔다.

3번째 방식을 택해도 같은 경우의 수가 나온다.

S	인원1	인원2	인원3	인원1	인원2	인원3	인원1	인원2	인원3
3	2	1	1	2	1	1	2	1	1
2	1	1	0	1	1	0	1	1	0
1	0	0	0	0	1	0	1	0	0
0	X	X	X	0	0	0	0	0	0

지금까지 총 3가지 방식을 택해봤다. 이제 규칙성을 찾아보자.

 

공통되는 구간이 보일 것이다.

S가 1일때 인원들이 소화 할 수 있는 곡이 0곡씩 남으면 앨범을 만들 수 없다.

S가 1일때 인원1이  소화 할 수 있는 곡이 1곡 남고 나머지 인원들은 없다면 앨범을 만들 수 있는 경우의 수는 1이다.

 

위와 같은 방식으로 우리가 구한 결과를 이용한다면,

S가 2일때 1 1 0만큼 소화할 수 있는 곡이 남는다면, 앨범을 만들 수 있는 경우의 수는 2이며,
S가 2일때 1 0 1만큼 소화할 수 있는 곡이 남는다면, 앨범을 만들 수 있는 경우의 수는 2이다.

만일 다음에 같은 경우에 도달한다면, 굳이 경우의 수를 구할 필요 없이, 위에서 구한 경우의 수를 그대로 이용하면 된다.

 

경우의 수의 합계를 구하기 위해 역순으로 경우의 수를 구하며, 중복을 방지하기위해 재귀와 dp를 이용해 아래와 같은 메서드를 만들었다.

static int getSum(int[][][][] dp, int S, int dotorya, int kesakiyo, int hongjun) {
    if (S < 0 || dotorya < 0 || kesakiyo < 0 || hongjun < 0) {
        return 0;
    }
    if (S == 0) {
        return (dotorya == 0 && kesakiyo == 0 && hongjun == 0) ? 1 : 0;
    }

    // 메모이제이션: 이미 계산된 경우
    if (dp[S][dotorya][kesakiyo][hongjun] != -1) {
        return dp[S][dotorya][kesakiyo][hongjun];
    }

    int sum = 0;

    // 재귀적으로 각 경우를 탐색하며 sum에 더해줌
    sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo, hongjun)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya, kesakiyo-1, hongjun)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya, kesakiyo, hongjun-1)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo-1, hongjun)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo, hongjun-1)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya, kesakiyo-1, hongjun-1)) % MOD;
    sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo-1, hongjun-1)) % MOD;

    // 결과를 메모이제이션 테이블에 저장
    dp[S][dotorya][kesakiyo][hongjun] = sum;

    return sum;
}

• 재귀 도중 S, 인원1, 인원2, 인원3이 소화할 수 있는 노래중 하나라도 음수가 되면 0을 반환한다.
• 만일 모두 0이라면, 경우의 수에 1이 늘어난다.
• dp테이블을 이용해 지금 과정이, 이전에 해본 과정이라면, 그전에 구해놓은 경우의 수를 이용한다.
• 재귀를 통해 각 과정에서 아래 표를 각 인원에 적용시킨다. S는 무조건 1씩 줄어든다.
  

  	인원 1	인원 2	인원 3
  1	O	O	O
  2	O	O	X
  3	O	X	O
  4	X	O	O
  5	O	X	X
  6	X	O	X
  7	X	X	O

  재귀를 통해 구해진 값은 아래 값으로 나눠서 sum에 저장한다.
  

  static final int MOD = 1000000007;

• 위의 표를 각 인원에 모두 적용시켜보았다면, 그 결과 나온 경우의 수를 dp 테이블에 저장해놓는다.
• 경우의 수가 모두 구해졌다면 반환한다.

위 재귀의 결과 모든 경우의 수를 중복없이 구할 수 있을 것이다.

 

전체코드:

import java.util.*;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int dotorya = sc.nextInt();
        int kesakiyo = sc.nextInt();
        int hongjun = sc.nextInt();
        int[][][][] dp = new int[S+1][dotorya+1][kesakiyo+1][hongjun+1];

        for (int[][][] arr3d : dp) {
            for (int[][] arr2d : arr3d) {
                for (int[] arr1d : arr2d) {
                    Arrays.fill(arr1d, -1);
                }
            }
        }

        System.out.println(getSum(dp, S, dotorya, kesakiyo, hongjun));
    }

    static int getSum(int[][][][] dp, int S, int dotorya, int kesakiyo, int hongjun) {
        if (S < 0 || dotorya < 0 || kesakiyo < 0 || hongjun < 0) {
            return 0;
        }
        if (S == 0) {
            return (dotorya == 0 && kesakiyo == 0 && hongjun == 0) ? 1 : 0;
        }

        // 메모이제이션: 이미 계산된 경우
        if (dp[S][dotorya][kesakiyo][hongjun] != -1) {
            return dp[S][dotorya][kesakiyo][hongjun];
        }

        int sum = 0;

        // 재귀적으로 각 경우를 탐색하며 sum에 더해줌
        sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo, hongjun)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya, kesakiyo-1, hongjun)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya, kesakiyo, hongjun-1)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo-1, hongjun)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo, hongjun-1)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya, kesakiyo-1, hongjun-1)) % MOD;
        sum = (sum + getSum(dp, S-1, dotorya-1, kesakiyo-1, hongjun-1)) % MOD;

        // 결과를 메모이제이션 테이블에 저장
        dp[S][dotorya][kesakiyo][hongjun] = sum;

        return sum;
    }
}

 

시행착오:

처음에는 너무 수학적으로 접근했다.

컴비네이션을 이용해서 경우의 수를 구하려고 했고, 수학적으로는 더 빨라보이는 접근이였지만, 
1000000007로 sum값을 나눠서 반환해야 한다는 문제점이 있었다.

여러 컴비네이션을 여러 사칙연산을 통해 계산해내야 했기 때문에, 1000000007로 나눈 나머지를 구하려면,
모듈러 함수, 모듈러 역원등의 개념을 제대로 이해 해야했다.

그 결과 코드도 복잡해지고, 모듈러를 이해하지 못해, 어느 부분이 잘못된것인지 예측할 수 없게 되었다.

 

두번째는 재귀를 이용했지만, dp를 이용하지 않았고, 그 결과 많은 중복이 발생해 시간 초과가 발생했다.

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int dotorya = sc.nextInt();
        int kesakiyo = sc.nextInt();
        int hongjun = sc.nextInt();

        System.out.println(getSum(S, dotorya, kesakiyo, hongjun));
    }

    static int getSum(int S, int dotorya, int kesakiyo, int hongjun) {
        if (S > dotorya + kesakiyo + hongjun) {
            return 0;
        }
        if (S == 0) {
            return (dotorya == 0 && kesakiyo == 0 && hongjun == 0) ? 1 : 0;
        }
        int sum = 0;
        if (dotorya > 0) {
            sum = (sum + getSum(S-1, dotorya-1, kesakiyo, hongjun)) % MOD;
        }
        if (kesakiyo > 0) {
            sum = (sum + getSum(S-1, dotorya, kesakiyo-1, hongjun)) % MOD;
        }
        if (hongjun > 0) {
            sum = (sum + getSum(S-1, dotorya, kesakiyo, hongjun-1)) % MOD;
        }
        if (dotorya > 0 && kesakiyo > 0) {
            sum = (sum + getSum(S-1, dotorya-1, kesakiyo-1, hongjun)) % MOD;
        }
        if (dotorya > 0 && hongjun > 0) {
            sum = (sum + getSum(S-1, dotorya-1, kesakiyo, hongjun-1)) % MOD;
        }
        if (kesakiyo > 0 && hongjun > 0) {
            sum = (sum + getSum(S-1, dotorya, kesakiyo-1, hongjun-1)) % MOD;
        }
        if (dotorya > 0 && kesakiyo > 0 && hongjun > 0) {
            sum = (sum + getSum(S-1, dotorya-1, kesakiyo-1, hongjun-1)) % MOD;
        }

        return sum;
    }
}

하지만, 접근 자체에는 문제가 없다고 느꼈고, 어떻게 하면 중복을 줄일 수 있을까 고민해보았다.

풀이 과정처럼 재귀 과정을 직접 작성해보니, 중복을 줄일 수 있는 방법을 찾을 수 있게 되었다.

 

이렇게 두번의 시행착오를 겪으며, 아직 재귀, dp 두 부분 모두 부족하다는 것을 알 수 있었다.

그래도 블로그를 작성하며, 문제에 대한 더 깊은 이해를 할 수 있었다.