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

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

12872번: 플레이리스트

위 문제는.. 접근하는 방법을 도저히 모르겠어서 답을 보고 한참을 생각했다가 풀었는데,

중간에 잘못생각한 코딩 몇글자..?로 한참을 또 생각한 문제였다ㅠㅠ

n개의 곡이 있고, p개의 곡을 들을건데, 중복되는 노래의 경우 반드시 m개의 곡을 사이에 두고 플레이 해야한다...

 

먼저, m개의 곡을 사이에 두고를 빼고 중복된 값이 안된다고 가정하면 가능한 경우의 수가

3개 곡인 경우 -> 3 x 2 x 1

5개 곡인 경우 -> 5 x 4 x 3 x 2 x 1

 

중복된 값이 가능하나 다른 m개의 곡을 반드시 사이에 둬야 한다고 보면

n = 3, m = 1, p = 5 인 경우

1) 처음에는 3 곡 중 하나가 가능 (남은 노래가 3, 그래서 한곡을 플레이 하면 * restPlay가 된다. 26번째 줄)

2) 두번째는 연속으로 중복된 곡이 나오면 안되므로 3개중 사용한 한 곡을 제외한 두 곡(남은 노래)중 하나가 가능

3) 세번째부터는 index(2)가 m 보다 커지므로 두가지의 경우로 나뉘어 질 수 있다.

→ 새로운 곡을 재생하는 경우(25번째 줄) vs 재생했던 곡을 플레이 하는 경우(28번째 줄)

- 새로운 곡을 재생하는 경우 : 남은 노래의 수 만큼의 경우의 수가 가능.

- 재생했던 곡을 플레이 하는 경우 : 전체 노래에서 중복되면 안되는 m개의 수를 빼고, 재생했던 곡을 플레이 하는 경우이기 때문에 남은 곡의 수도 제외한 수 만큼의 경우의 수가 가능.

 

내가 잘못코딩해서 한참을 헤맸던 부분이 재생했던 곡을 플레이하는 경우, 전체 노래에서 m을 빼고 남은 노래도 빼는 경우..!(29번 줄 n-m-restPlay) 나는 m만 제외하고 남은곡을 제외해야 하는 것을 빠트려서.. 한참을 헤맸다..하

 

경우의 수를 잘 생각해서, 새로운 노래을 추가하는 경우와 기존에 재생했던 노래를 추가하는 경우일 때, 기존에 재생했던 노래라면 남은 노래의 수를 빼야한다는 것, 다음부터는 이런거 놓치지 말자.