[백준] 12872 플레이리스트

문제보기

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

public class Main{
  // 차례대로 담긴 총 곡 수, 이미 추가된 곡 수 일 때 가능한 경우의 수를 담는 변수 
  static long[][] d;
  static int n, m, p;
  static final long mod = 1000000007;


  static long go(int idx, int x){
    // y 는 아직 플레이 리스트에 담기지 않은 노래의 갯수
    int y = n-x;
		
    // idx는 0부터 시작했기 때문에 p이면 이미 다 담긴 것임
    if( idx == p ){
      // 아직 플레이 리스트에 담기지 않은 노래는 없어야한다
      if( y == 0 ) return 1;
      // 아직 있다면 불가능한 경우 - 0 반환
      else return 0;
    }
		
    // 메모된 값이 있다면 갖다 쓰자
    if(d[idx][x] != -1){
      return d[idx][x];
    }
		
    // 모든 경우의 수를 담을 변수
    long ans = 0;

    // 아직 한번도 안 담긴 곡이 있다면
    if( y > 0 ){
      // 이 곡을 넣는 모든 경우의 수는 yC1 이므로
      ans += go(idx+1, x+1)*y;
    }

    // 이미 담긴 곡 수가 m개를 초과한다면, 
    // 끝에서부터 m+1번째 곡~ 첫곡 까지는 한번 더 담겨도 되는거잖아?
    if( x > m ){
      ans += go(idx+1, x) * (x-m);
    }

    ans %= mod;
    d[idx][x] = ans;
    return ans;
  }


  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());
    d = new long[p+1][n+1];

    for(int i = 0 ; i <= p ; i++ ){
      Arrays.fill(d[i], -1);     
    }

    System.out.println(go(0, 0));

  }
}

d 설정 시 어떤게 기준이 되어야 할지가 아직 확실하게 잡히질 않는다

한 30개쯤 더 풀어보자..!