[백준/JAVA] 12872번: 플레이리스트

📖 문제

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

 

 

💡  풀이 방식

• DP

DP[ i ][ j ] : i개의 음악을 플레이리스트에 넣고, j개의 음악 종류를 사용했을 때의 경우의 수

 

어떤 집합에서 아무거나 하나를 놓으면 된다

= 어떤 집합의 원소의 수를 곱한다

 

 

음악은 플리(플레이리스트)에 넣었는지 여부에 따라 2가지 종류로 나눌 수 있다.

 

1) 플리에 넣지 않은 음악인 경우

  - 아직 플리에 넣지 않았으므로, 같은 노래 사이에 M개의 곡이 있어야 한다는 2번 조건은 고려할 필요가 없다.

  - 대신 이전 모든 경우의 수들에 추가될 수 있으므로 아래와 같은 점화식이 도출된다.

dp[musicNum][savedMusicNum] += dp[musicNum - 1][savedMusicNum - 1] + (N - savedMusicNum + 1)

 

 

 

2) 플리에 넣은 음악인 경우

  - 같은 노래 사이에 M개의 곡이 있어야 한다는 2번 조건을 반영한다.

  - 사용된 곡 종류가 M개를 초과하는 경우, 2번 조건을 충족해야 하므로 아래와 같은 점화식을 도출할 수 있다.

dp[musicNum][savedMusicNum] += dp[i-1][j] * (savedMusicNum - M)

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MOD = 1_000_000_007;
    static int N,M,P;
    static long[][] dp = new long[101][101];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        
         // dp[i][j] : i개의 음악을 플리에 넣고, j개의 음악 종류를 사용했을 때의 경우의 수
        dp[0][0] = 1;
        
        for(int musicNum = 1 ; musicNum <= P ; musicNum++) {
            for(int savedMusicNum = 0 ; savedMusicNum <= N ; savedMusicNum++) {
                if(savedMusicNum > 0) { // 1) 플리에 넣지 않은 음악인 경우
                    dp[musicNum][savedMusicNum] += dp[musicNum-1][savedMusicNum-1] * (N - savedMusicNum + 1);
                    dp[musicNum][savedMusicNum] %= MOD;
                }
                if(savedMusicNum > M) { // 2) 플리에 넣은 음악인 경우
                    dp[musicNum][savedMusicNum] += dp[musicNum-1][savedMusicNum] * (savedMusicNum - M);
                    dp[musicNum][savedMusicNum] %= MOD;
                }
            }
        }
        
        System.out.println(dp[P][N]);
    }
}
 

 

 

---

💦 어려웠던 점

- 점화식 도출하는 부분,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

BOJ 12872번 플레이 리스트

[BaekJoon] 12872 플레이리스트 (Java)