[백준 - 12996번] Acka - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

입력

첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)

출력

첫째 줄에 앨범을 만들 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

풀이

앨범을 만들 수 있는 모든 경우의 수를 구해야 한다.
앨범은 참여한 사람이 다른 곡이 존재하면 다른 앨범으로 취급한다.

조합을 이용한 풀이?

나는 처음에 조합을 이용한 풀이를 생각했다.

dotorya가 곡을 선택하는 경우의 수는 전체 곡에서 불러야 하는 곡의 수를 뽑는 경우의 수가 된다.

다음 kesakiyo가 곡을 선택하는 경우의 수는
아직 선택되지 않은 곡을 하나 선택하는 경우 (나머지 횟수는 이미 선택된 곡에서 조합을 구하면 됨)
아직 선택되지 않은 곡을 두 개를 선택하는 경우
...

이런 식으로 반복이 된다.

다음 hongjun7이 곡을 선택하는 경우의 수는 나머지 선택되지 않은 곡을 전부 선택해야 되며 그 나머지 횟수는 이미 선택된 곡에서 조합을 구한다.

각 가수가 곡을 선택하는 경우의 수를 다 곱해주면 답이 된다.

이 풀이를 구현하려면 50!을 담아야 하기 때문에 문제가 복잡해 지고, DP 풀이가 아니기 때문에 다른 방법을 생각해 봤다. 그래서 이 풀이가 되는지는 모른다. 아마 시간 복잡도는 O(S^2) 정도 될 것 같다.

dp를 이용한 풀이

곡을 만드는 경우의 수는 다음과 같다. (dotorya는 0, kesakiyo는 1, hongjun7는 2라고 하겠다.)

{0}, {1}, {2},
{0, 1}, {0, 2}, {1, 2},
{0, 1, 2}

총 7가지다.

그러면 모든 경우의 수를 구하려면 약7^50정도로 불가능하다.

그런데 생각해 보면

남은 곡,
dotorya가 불러야 하는 남은 곡 횟수,
kesakiyo는 불러야 하는 남은 곡 횟수,
hongjun7는 불러야 하는 남은 곡 횟수
가 같다면 구하는 경우의 수는 같을 것이다.

그래서 이를 이용하면 중복 계산을 없애 줄 수 있고, 시간 복잡도가 O(50^4)로 가능한 풀이가 된다.

구체적인 구현은 풀이를 이해했다면 코드로도 잘 이해가 될 것이다.

소스 코드

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

public class Main {
    static final int MOD = 1000000007;
    static final int[][] CASE = {
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1},
        {1, 1, 0},
        {1, 0, 1},
        {0, 1, 1},
        {1, 1, 1}
    }; //곡을 만드는 경우의 수는 7가지
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      int S = Integer.parseInt(st.nextToken());
      int d = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      int h = Integer.parseInt(st.nextToken());
      
      int[][][][] dp = new int[S + 1][d + 1][k + 1][h + 1];
      
      System.out.println(answer(S, d, k, h, dp));
  }
  
  static int answer(int S, int d, int k, int h, int[][][][] dp) {
      if(d == -1 || k == -1 || h == -1 || dp[S][d][k][h] == -1) {
          //안되는 경우에는 -1, -1은 방문은 했지만 경우의 수가 존재하지 않음
          return 0;
      }
      
      if(dp[S][d][k][h] > 0) {
          //이미 방문을 했고, 경우의 수가 존재함
          return dp[S][d][k][h];
      }
      
      if(S == 0) {
          if(d == 0 && k == 0 && h == 0) {
              return 1;
          }
          return 0;
      }
      
      long v = 0;
      for(int i=0; i<7; i++) {
          v += answer(S - 1, d - CASE[i][0], k - CASE[i][1], h - CASE[i][2], dp);
      }
      
      if(v == 0) {
          dp[S][d][k][h] = -1;
          return 0;
      }
      dp[S][d][k][h] = (int) (v % MOD);
      return dp[S][d][k][h];
  }
}