컴소 최고의 피아니스트 예원이는 오른손만으로도 모든 곡을 연주할 수 있다. 비결은 손을 최대한 조금 움직이는 것이다.

예원이가 연주하는 피아노에는 200\, 000개의 흰 건반만 있으며, 가장 왼쪽 건반부터 순서대로 1, 2, \cdots, 200\, 000까지의 번호가 차례대로 매겨져 있다. 예원이의 손 길이는 흰 건반 K개만큼이며, 다음에 치려는 건반이 손 안에 있다면 손을 움직이지 않고 다음 음을 낼 수 있다. 예를 들어, 손 길이가 건반 5개만큼이고 오른손 엄지를 1번 건반에 두었다면 1번 건반부터 5번 건반까지는 손을 움직이지 않고 칠 수 있지만, 이 범위를 벗어나는 건반을 누르려면 손을 다른 위치로 옮겨야 한다.

다음 곡을 연주하려면 N개의 흰 건반을 순서대로 눌러야 한다. 예원이는 원하는 위치에 손을 두고 연주를 시작하며, 연주 중 필요할 때만 손을 옮길 것이다. 하지만 예원이는 수많은 과제에 시달리느라 악보를 분석할 시간이 없다. 바쁜 예원이 대신 곡을 연주하기 위해 손을 옮겨야 하는 최소 횟수를 구하는 프로그램을 작성해 주자!

#8197 upload 2 done 1 how_to_reg 1 call_split Subtask

피아노 timer 1s memory 1024MB

#8197
Subtask

피아노 1s 1024MB