BOJ 15397 Looping Playlist
BOJ 15397 Looping Playlist
문제 내용
1개 이상의 음악을 포함하는 어떤 플레이리스트가 무한 반복 재생되고 있습니다. 특정 시점부터 한 바퀴 동안 재생된 모든 음계가 순서대로 주어질 때, 이 플레이리스트에 포함된 음악의 개수의 최솟값을 구하세요.
음계는 Do, Do#, Re, Re#, Mi, Fa, Fa#, Sol, Sol#, La, La#, Si의 12종류가 있으며, Si의 다음 음계는 Do로 반복됩니다.
하나의 음악은 하나의 장조에 속하는 음계만으로 이루어져 있으며, 하나의 장조에는 기준음 를 기준으로 의 음계가 포함됩니다.
입력
첫 줄에는 음계의 개수 이 주어집니다. ()
다음 줄에는 음계가 한 줄에 하나씩 주어집니다. 모든 음계의 스펠링과 대소문자는 위의 지문과 일치합니다.
출력
문제의 정답을 출력합니다.
문제 풀이
스포일러
이어도 굉장히 빡빡한 시간 제한을 가지고 있는 문제입니다.
먼저 원형이 아닌 선형일 때의 그리디를 생각해 봅시다. 그러면 단순히 앞에서부터 최대한 많은 음을 포함하는 장조를 찾고, 다음 음에서 시작하는 것을 반복하면 됩니다. 구현은 각 음계가 속할 수 있는 장조의 목록 을 비트마스크로 두면 상수를 최소화할 수 있습니다.
그럼 원형일 때는 어떻게 해야 할까요?
첫 음을 포함하는 장조는 총 7개가 있습니다. 각각의 경우로 나누어서 그리디를 한 뒤에, 맨 뒤의 구간이 첫 음에 줬던 장조에 포함되면 1을 빼 줄 수 있습니다. 이들 결과 중에서 최솟값을 출력하면 됩니다.
다음의 그리디는 현재 데이터에서 통과하지만, 반례가 있습니다.
- 먼저 시작점에서 시작하여 선형 그리디를 한 번 진행합니다.
- 선형 그리디에서 마지막 구간의 시작점에서 시작하여 선형 그리디를 한 번 더 진행합니다.
- 두 결과의 최솟값을 출력합니다.
Last updated on