백준 2841번 Pseudo code

문제 링크

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

2841번: 외계인의 기타 연주

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

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

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

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

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

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

 

입력

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

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

출력

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

 

예제 입력

5 15
2 8
2 10
2 12
2 10
2 5

예제 출력

7

문제 풀이를 위해 생각한 것

1. 1번부터 6번 줄까지 독립적으로 관리해야 한다.
2. 현재 누르고 있는 최대값의 음이 표현된다.
3. 표현해야 하는 음이 현재보다 높은 값이면 이미 잡고 있던 손가락을 떼지 않고 추가로 누를 수 있다.
4. 표현해야 하는 음이 현재보다 낮은 값이면 잡고 있는 음이 표현해야 하는 음보다 낮거나 같을 때까지, 혹은 아예 손가락을 잡고 있지 않을 때까지 손가락을 떼야 한다.
5. 원소를 삽입하고, 삭제할 때 이미 대소비교를 하기 때문에 스택을 사용할 수 있다.

 

사용한 자료구조

스택.

삽입 삭제 연산이 빈번하게 일어난다. 최대 500,000번까지 일어날 수 있다. 따라서 삽입, 삭제가 O(1)인 스택을 사용한다.

표현하고자 하는 값이 현재의 최댓값보다 크면 pop하고, 작으면 바로 push를 한다는 점에서 스택을 활용할 수 있다.

또한 줄이 총 6개로 제한되어 있기 때문에 총 6개의 스택을 활용할 수 있다.

 

풀이 코드

n, p = 첫 입력값을 split하여 정수로 변환
총 6개의 스택 자료구조 stk_n을 선언
cnt = 0

n번 동안:
	n, p = 각 입력을 스택번호, 프렛번호로 저장
	if n번째 스택에 원소가 없으면:
		stk_n.push(p)
		cnt += 1
	elif n번째 스택에 원소가 있으면:
		if stk의 최상단 원소가 p보다 작으면:
			stk.push(p)
			cnt += 1
		elif stk의 최상단 원소가 p보다 크면:
			stk의 최상단 원소가 p보다 작거나 같을 때까지, 혹은 원소가 없을때까지:
				stk.pop()
				cnt += 1
			if 최상단 원소 == p:
				continue
			else:
				stk.push(p)
				cnt += 1
		elif stk의 최상단 원소 == p:
			continue
print cnt

 

시간 복잡도 분석

O(NM). 문제에서는 O(NP).

O(1)의 스택 삽입, 삭제 연산을 최대 N번 동안, 최악의 경우 M번 수행(높은 음을 잡고 있는데, 표현해야 하는 음은 최하단일때)

(N ≤ 500,000, 2 ≤ P ≤ 300,000)

 

문제에서 중요한 부분

삽입 삭제 연산이 빈번하게 일어나는 문제이다. N의 크기와 자료구조별 삽입, 삭제 연산의 시간 복잡도가 주요 고려 사항이었다.