문제 링크
https://www.acmicpc.net/problem/12872
🕒 Python 풀이시간: x
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])🎶 플레이리스트의 수학적 마법: DP로 푸는 노래 고르기 🧮
도대체 이런건 어떻게 생각해내서 푸는건지 참...
j는 현재까지 선택한 노래의 집합이다. 즉 중복을 제외하고 따지는 것이다. 그리고 i는 플레이리스트에 지금까지 추가한 곡의 갯수이다.
특정 노래를 골랐을 때의 가짓수에서 다음 노래를 고르는 가짓수를 곱해주는게 현재 자리까지의 노래를 고르는 종류이기 때문에 곱셈을 사용해준다.
처음의 모든 가짓수는 0이기 때문에 dp 배열을 0으로 해주며 아무 노래도 선택하지 않은 경우는 1가지 이므로 dp[0][0]은 1로 둔다.
먼저 어떤 경우에서든지 우리는 아직 선택되지 않은 노래 중에 한가지를 고를 수 있다. 그 경우는 현재까지 선택한 노래의 집합에서는 아직 선택하지 않은 노래이기 때문에 -1이 된 상태이고 지금까지 추가한 곡의 갯수에서도 -1을 한 상태인 dp[j-1][i-1]인 상태인 것이다. 이 경우에서 다음 곡을 고른다고 했을 때는 전체 곡에서 현재까지 골랐던 노래인 j-1개의 노래를 제외한 나머지 중에서 선택하는 것이기에 (n-(j-1))가지 중에 고르는 것이다. 그렇기에 곱셈을 해주어 더해준다.
그런 다음 j>m이라는 조건이 있다. 우리는 같은 곡을 고를 때에는 중간에 무조건 m개의 노래가 있어야 한다. 이러한 조건은 모든 곡에 적용되므로 m개의 연속된 구간에서는 서로 다른 곡들만 존재한다는 뜻이 된다. 그렇기에 아직 j가 즉, 지금까지 고른 노래의 집합이 m개가 되지 않는다면 아직 같은 노래를 고를 수 없는 것이라는 뜻이다. 아직 처음 중복이 한 번 더 될 정도의 갯수도 뽑지 않았다는 뜻이니까 말이다. 즉 j>m이 된다면 새로운 경우를 뽑을 수 있다. 즉 이전에 뽑았던 노래 중에 중복해서 뽑을 수 있는 것인데 이 때의 dp 상태를 먼저 보자. 현재 뽑았던 집합중에 중복해서 뽑아보는 것이기에 j의 값은 그대로이고 지금까지 뽑은 노래의 갯수에서는 -1을 해준 상태인 dp[j-1][i]가 된다. 이제 노래를 뽑아야 할 경우인데 방금 연속된 m개의 구간에서는 같은 노래가 있을 수 없다고 했다. 그렇기에 지금 뽑아야 되는 지점으로부터 m개전까지의 집합에서는 뽑을 수 없다는 것이다. 중간에 m개의 곡이 올 수 없기 때문이다. 그렇기에 j개의 집합에서 m개의 노래를 제외하고 그 중에서 뽑는 (j-m)을 곱해주는 상태가 된다.
내가 시도한 방법은 DFS로 먼저 접근했다가 재귀를 DP로 변환하면 풀 수 있지 않을까 했다. 즉 백트래킹으로 모든 방법을 누적하는 방법으로 풀어보려고 했지만 마지막 위치를 기록하는 방법으로는 dp를 사용하면 메모리 초과가 발생하였다. 곱셈을 사용해서 dp를 직접적으로 중복뽑기라는 점을 사용해서 뽑는 문제는 처음인거 같다. 접근 방법에 접근 조차 제대로 하지 못하였다 ㅠ
이렇게 Python로 백준의 "플레이리스트" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
