[Python 파이썬] 백준 2841번 - 외계인의 기타 연주

2024년 7월 31일

문제 링크 : 백준 2841번 - 외계인의 기타 연주

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다. 줄의 번호는 N보다 작거나 같은 자연수이고, 프렛의 번호도 P보다 작거나 같은 자연수이다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

 

 

 

알고리즘 분류

• 자료 구조
• 스택

---

 

문제 접근

 

문제를 잘 읽어보면 다음과 같이 정리할 수 있다.

 

1. 기타는 1번 ~ 6번의 총 6개의 줄을 가지고 있다. 이는 6개의 음계가 독립적으로 존재한다고 이해할 수 있다.

2. 각 줄에는 P개의 프렛이 존재한다.

3. 같은 줄에 3번 프렛, 5번 프렛에 손가락을 올려놓고 있으면, 번호가 더 큰 5번 프렛의 음만 유효하다.

4. 유효한 손가락 움직임은 프렛을 한 번 누르거나 떼는 것 뿐이다.

5. 문제에서 요구하는 연주란, 주어진 멜로디 순서대로 모두 소리가 나게끔만 하면 된다.

 

특히, 5번 사항을 제대로 이해하지 못해 코드를 한 번 갈아엎었었다.

 

2번 줄의 특정 프렛을 누른 상태에서 1번 줄의 어떠한 프렛 음을 내려면 2번 줄에 올린 손가락을 모두 떼고 1번 줄의 프렛에 손을 올려야 한다고 이해하는 잘못된 접근을 했던 것이다.

 

2번 줄의 특정 프렛에 손가락이 눌려있는 상태라도, 다른 줄의 특정 프렛에 손가락을 올리면 해당 음은 정상적으로 소리가 나게 되는게 이 문제의 전제 조건이다.

 

---

입력 예제

 

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

 

 

 

각 기타의 줄을 음계라고 표시하였고, 각 줄은 독립적이기에 각 음계에 현재 눌려있는 프렛을 각 스택에 담아낼 것이다.

 

위 입력 예시는 1, 2번 음계만 사용되었으므로 3 ~ 6 음계는 표기를 생략하겠다.

 

 

now_level은 현재 연주하고 싶은 멜로디의 음계이며,

now_fret은 현재 연주하고 싶은 멜로디의 프렛이다.

또한, cnt는 손가락을 움직인 총 횟수이다.

 

 

1음계 스택이 비어있으므로, 해당 멜로디를 연주하려면 1음계의 5번째 프렛을 손가락으로 누르기만 하면 된다.

그러므로 1음계 스택에 5번째 프렛을 append 해준다.

또한, 프렛을 손가락으로 누르는 작업이 수행되었으므로 cnt를 1 증가시킨다.

 

 

그 다음 멜로디의 음계는 2이고, 프렛은 3번째 프렛을 눌러야 한다.

 

 

2음계 스택이 비어있으므로 3번째 프렛을 누르기만 하면 되기 때문에 2음계 스택에 3번째 프렛을 append 해준다.

프렛을 손가락으로 누르는 작업이 수행되었으므로 cnt를 1 증가시킨다.

 

 

그 다음 멜로디의 음계는 2이며, 프렛은 5번째 프렛을 눌러야 한다.

 

 

스택에서 가장 큰 프렛 번호는 스택의 가장 마지막에 위치할 수 밖에 없다.

스택의서 가장 큰 프렛 번호가 현재 연주하고 싶은 멜로디의 프렛보다 작기 때문에 추가로 5번째 프렛을 손가락으로 눌러주기만 하면 된다.

손가락으로 프렛을 눌렀으므로 cnt를 1 증가시킨다.

 

 

그 다음 멜로디의 음계는 2이며, 7번째 프렛을 눌러야 한다.

 

 

2음계에서 가장 큰 프렛의 번호는 5이므로, 현재 연주하고 싶은 멜로디의 프렛보다 작기 때문에 추가로 7번째 프렛을 손가락으로 눌러주기만 하면 된다.

손가락으로 프렛을 눌렀으므로 cnt를 1 증가시킨다.

 

 

그 다음 연주하고 싶은 멜로디의 음계는 2이며, 4번째 프렛을 눌러야 한다.

 

 

2음계 스택의 마지막 요소보다, 현재 연주하려는 멜로디의 프렛 번호가 더 작기 때문에 연주하려는 프렛의 번호보다 큰 모든 프렛의 번호에서 손가락을 떼는 작업을 수행해야 한다.

손가락을 뗄 때마다 cnt를 1 증가시켜준다.

 

 

4번째 프렛을 눌러주는 작업을 추가로 수행해야하므로 2음계 스택에 4번 프렛을 추가시켜주고 cnt를 1 증가시켜준다.

 

 

그 다음 연주하고 싶은 멜로디의 음계는 1이며, 5번째 프렛을 눌러야 한다.

 

1음계 스택의 마지막 요소가 현재 연주하고 싶은 프렛의 번호와 같다. 이미 해당 음은 연주되고 있는 상태이다.

그러므로 손가락을 움직이지 않고 해당 음을 연주했으므로 연산을 생략하고 넘어간다.

 

 

그 다음 연주하고 싶은 멜로디의 음계는 1이며, 3번째 프렛을 눌러야 한다.

 

 

1음계 스택의 마지막 요소가 현재 연주하고 싶은 프렛의 번호보다 크므로, 1음계에 눌려있는 더 큰 번호의 프렛에서 손가락을 모두 떼주는 작업을 수행해야 한다.

 

 

추가로 현재 연주하고 싶은 프렛의 번호를 손가락으로 눌러주어야 하므로 1음계에 3번째 프렛을 append하고 cnt를 1 증가시킨다.

 

모든 멜로디를 순서대로 연주하였으므로 cnt를 출력하고 로직을 종료한다.

 

출력 예제

 

9

 

 

---

전체 코드

 

# 2841
import sys
input = sys.stdin.readline

def solution():
    cnt = 0
    # 각 음계의 어느 프렛에 손가락이 올라가있는지 확인하기 위한 6개의 스택 선언
    # 0번째 스택은 더미 스택
    stack = [[] for _ in range(7)]

    for idx in range(N):
        now_level, now_fret = melody[idx]
        if not stack[now_level] or stack[now_level][-1] < now_fret:
            stack[now_level].append(now_fret)
            cnt += 1
        else:
            while stack[now_level] and stack[now_level][-1] > now_fret:
                stack[now_level].pop()
                cnt += 1
            if not stack[now_level] or stack[now_level][-1] < now_fret:
                stack[now_level].append(now_fret)
                cnt += 1

    return cnt


if __name__ == "__main__":
    N, P = map(int, input().split())
    melody = []
    for _ in range(N):
        melody.append(list(map(int, input().split())))

    print(solution())

 

---

풀이 후기

 

프렛 말고, 음 또한 높은 음만 유효하다고 이해하고 문제에 접근했다가 코드를 갈아엎었었다.

문제가 제시하는 바를 명확히 이해하는 과정이 가장 중요했다고 생각한다.