기타 연주(GITARA) timer 1초 memory 32MB

영호는 최근 손가락을 1억개나 가지고 있는 상상속의 외계인 친구를 알게 되었다. 이 외계인 친구는 기타를 가지고 있었고 영호를 위해 연주를 시작했다.

아래 그림과 같이 기타는 일반적으로 6개의 줄을 가지고 있다. 각 줄을 편의상 1번에서 6번 으로 부르기로 한다. 또한 각 줄은 프렛을 공유하여 가지고 있다. 각각의 프렛을 편의상 1번에서 P번으로 부르기로 한다.

멜로디(소리의 높낮이)는 프렛를 누르는 것에 따라 다르게 나온다. 물론 프렛과 프렛사이를 손라락으로 누른뒤 해당 줄을 튕겨 소리를 내는 것이 일반적이다. 문제에서는 편의상 프렛의 위치를 누르는 것으로 한다.

하나의 줄에서 여러개의 프렛을 누르게 되면 그 중 가장 높은 음만 나오게 된다. 예를 들어 2번 줄에 2번 프렛, 3번 프렛, 6번 프렛을 함께 누르고 2번 줄을 튕기게 되면 6번 프렛에 해당하는 음만 나온다는 것이다. 이 상태에서 3번 프렛에 해당하는 음을 내고 싶다면 6번 프렛을 누르고 있던 손가락을 떼야 한다. 외계인 친구는 한번에 하나의 음만 낸다. 하지만 손가락이 많으므로 여러개의 프렛을 계속 누르고 있을 수가 있다.(힘도 세다.^^)

외계인 친구가 주어진 멜로디를 낼 때 누르거나 떼는 횟수의 최소값을 구하는 프로그램을 작성하시오. 기타줄을 튕기는 것은 횟수에 포함시키지 않는다.