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

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int DIVISOR = 1_000_000_007;
    static int N;
    static int M;
    static int P;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt(); // 노래 종류의 수
        M = scanner.nextInt(); // 같은 노래 사이에 있어야 하는 곡의 수
        P = scanner.nextInt(); // 플레이리스트에 들어갈 노래의 수
    }

    static void solution() {
        // 플레이리스트의 경우의 수
        // playlists[musicNum][savedMusicNum]
        //  -> musicNum개의 음악을 플레이리스트에 넣고 savedMusicNum개의 음악 종류를 사용했을 때의 경우의 수
        long[][] playlists = new long[P + 1][N + 1];
        calculatePlaylistNum(playlists); // 플레이리스트를 만들 수 있는 경우의 수 구하기
        System.out.println(playlists[P][N]);
    }

    static void calculatePlaylistNum(long[][] playlists) {
        playlists[0][0] = 1L;

        // 점화식 구하기
        //  - 음악은 크게 두 가지의 종류로 나눠볼 수 있다 -> 플레이리스트에 넣은 음악, 플레이리스트에 넣지 않은 음악
        //  - 플레이리스트에 넣지 않은 음악
        //      - 아직 플레이리스트에 넣지 않았기 때문에 문제의 조건 중 같은 노래 사이에 M개의 곡이 있어야 한다는 조건에는 해당하는 사항이 없다
        //      - 그러므로 해당 음악들은 이전 모든 경우의 수들에 추가될 수 있으니 아래와 같은 점화식이 나올 수 있다
        //          - playlists[musicNum][savedMusicNum] = playlists[musicNum][savedMusicNum] + ((N - savedMusicNum + 1) * playlists[musicNum - 1][savedMusicNum - 1])
        //  - 플레이리스트에 넣은 음악
        //      - 이 음악들은 문제의 조건 중 같은 노래 사이에 M개의 곡이 있어야 한다는 조건에 해당하는 사항이 있기 때문에 이를 고려해주어야 한다
        //      - 위 말을 생각해보면, 같은 두 노래 사이에 있는 M개의 곡에는 같은 곡이 포함될 수 없다. 즉, M개의 곡은 모두 서로 다른 종류의 곡이다
        //      - 그러므로 사용된 곡의 종류가 M개 이하인 경우에는 위 조건이 성립될 수 없기 때문에 이 경우는 경우의 수를 더해주지 않고
        //      - 사용된 곡의 종류가 M개 초과인 경우에는 위 조건을 성립시킬 수 있기 때문에 이러한 경우에는 아래와 같은 점화식이 나올 수 있다
        //          - playlists[musicNum][savedMusicNum] = playlists[musicNum][savedMusicNum] + (savedMusicNum - M) * playlists[musicNum - 1][savedMusicNum]
        //      - M개의 종류의 곡은 같은 노래 사이에 M개의 곡이 있어야 한다라는 조건에 의해 새로 추가할 곡에 포함될 수 없으므로 그 음악을 제외한 나머지 음악 종류들 중 하나를 넣어야 한다
        //      - 그렇기 때문에 위와 같은 점화식이 생성된다
        for(int musicNum = 1; musicNum <= P; musicNum++) {
            for(int savedMusicNum = 1; savedMusicNum <= N; savedMusicNum++) {
                playlists[musicNum][savedMusicNum] += (N - savedMusicNum + 1) * playlists[musicNum - 1][savedMusicNum - 1];
                playlists[musicNum][savedMusicNum] %= DIVISOR;

                if(savedMusicNum > M) {
                    playlists[musicNum][savedMusicNum] += (savedMusicNum - M) * playlists[musicNum - 1][savedMusicNum];
                    playlists[musicNum][savedMusicNum] %= DIVISOR;
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}