[백준] 12872. 플레이리스트 (파이썬)

문제

수빈이는 BOJ 알고리즘 캠프에서 음악을 들으면서 문제를 풀고 있다. 지금 수빈이의 스마트폰에는 N개의 노래가 저장되어 있다. 오늘 수빈이는 P개의 노래를 들으려고 한다. 수빈이는 다음과 같은 조건을 만족하는 플레이리스트를 만들려고 한다. 플레이리스트에는 같은 노래를 여러 번 추가해도 된다.

• 모든 노래를 플레이리스트에 추가해야 한다.
• 같은 노래를 추가하려면, 플레이리스트에서 두 노래 사이에 적어도 M개의 곡이 있어야 한다.

수빈이는 플레이리스트를 만들 수 있는 경우의 수가 궁금해졌다. N, M, P가 주어졌을 때, 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, P가 주어진다. (1 ≤ N ≤ 100, 0 ≤ M ≤ N, N ≤ P ≤ 100)

출력

첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1 0 3

예제 출력 1

1

예제 입력 2

1 1 3

예제 출력 2

0

예제 입력 3

2 0 3

예제 출력 3

6

예제 입력 4

2 1 4

예제 출력 4 복사

2

 

 

 

문제 링크

---

풀이

Dynamic Programming

 

dp[i][j]

- `i` : 현재까지 사용한 노래의 수
- `j` : 선택할 남은 노래의 수

 

• 초기화
  • `dp[0][0] = 1` : 아무 노래도 선택하지 않은 경우는 항상 1가지 경우가 있다.
• 점화식 
  1. 현재 위치에서 M번째 이후의 노래만 선택 가능한 경우
     • dp[j-1][i-1] * (n - (j-1))
       : 현재 위치에 새로운 노래를 추가할 때, 선택할 수 있는 노래의 개수는 남은 전체 노래 수에서 현재 위치 이전의 모든 노래 수를 제외한 것이다.
  2. 현재 위치에서 M번째 이전의 노래도 선택 가능한 경우
     • dp[j][i-1] * (j-m)
       : 현재 위치에 새로운 노래를 추가할 때, 선택할 수 있는 노래의 개수는 현재 위치까지의 노래 수에서 M번째 이전까지의 노래 수를 제외한 것이다.
• 결과
  • `dp[n][p]`를 반환한다.

  예시 : n, m, p = 2, 1, 4

  dp = [[1,0,0,0,0],
            [0,2,0,0,0],
            [0,0,2,2,2]]

  dp[0][0] = 1
    - 노래를 하나로 선택하지 않는 경우
  
  dp[1][1] = 2
    - [music1], [music2] 로 경우의 수는 2가 된다.
  
  dp[2][2] = 2
    - [music1, music2], [music2, music1]
  
  dp[2][3] = 2
    - [music1, music2, music1]
    - [music2, music1, music2]
  
  dp[2][4] = 2
    - [music1, music2, music1, music2]
    - [music2, music1, music2, music1]

 

n, m, p = map(int,input().split())

dp = [[0]*(p+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(1, p+1):
    for j in range(1, n+1):
        dp[j][i] += dp[j-1][i-1] * (n - (j-1))
        if j > m:
            dp[j][i] += dp[j][i-1] * (j-m)
        dp[j][i] %= 1000000007

print(dp[n][p])