[2841] 외계인의 기타 연주 (자료구조, Stack)

외계인의 기타 연주 2841번

문제

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

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

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

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

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

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

2841번: 외계인의 기타 연주

 

입력

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

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

 

출력

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

예제 입력 1

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

예제 출력 1

7

예제 입력 2 

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

예제 출력 2 

9

 

풀이과정 및 코드

구현 로직! (수작업..ㅎ)

✨나만의 Point✨

- 사용하는 메모리의 최소화를 위해 입력받는 횟수와 지정하는 프렛 수 둘 중에 작은 값으로 동적할당을 진행했다.

- 함수 간 파라미터 중첩을 방지하고자 전역변수를 사용하지 않았다.

 

/*
 
<풀이과정 - 스택 활용>
 
1. 이중 배열 포인터 변수로 6개의 Stack을 동적할당 한다.
 
2. stack의 top에 있는 인자를 보고 아래 연산을 수행한다.
 
1) top == -1 인 경우 (저장된 인자가 없는 경우) push, result++
 
2) top에 있는 인자가 pr보다 큰 경우 push, result++
 
3) top에 있는 인자가 pr보다 작은 경우 pop, result++
 
*/
 
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
 
int push(int stack[], int value, int top); //스택에 인자를 넣는 함수
int pop(int stack[], int top); //스택에 인자를 pop하는 함수
 
int main() {
int top_arr[6] = { -1,-1,-1,-1,-1,-1 }; //6줄 각각의 top 지정
int N, P, li, pr, size, result = 0; //차례로, 총 횟수 N, 프렛 P, 결과값 result  변수 정의
int **line; // 이중 배열 포인터로 줄 별 프렛을 저장할 변수 정의
line = (int**)malloc(sizeof(int*) * 6); // 줄 갯수로 행 동적할당
scanf("%d %d", &N, &P); //N,P 입력
 
size = (N>P) ? P:N ; //메모리 최소화 위한 동적할당 size 선정
 
//각 열을 N만큼 동적할당
for (int i = 0; i < 6; i++){
line[i] = (int*)malloc(sizeof(int) * size);
}
 
for(int i = 0; i < N; i++) //횟수 만큼 반복
{
scanf("%d %d", &li, &pr); //줄, 프렛 입력
 
for (int k = top_arr[li - 1]; k >= -1; k--) { //저장된 인자 수 만큼 반복
 
if (top_arr[li - 1] == -1) { //해당 줄 배열에 아무 인자도 없을 때
 
top_arr[li - 1] = push(line[li - 1], pr, top_arr[li - 1]); //첫번째 인자를 push 하기
result++;//시행+1
}
else if (line[li - 1][k] > pr) {//맨 위에 저장된 인자 값이 클 경우
top_arr[li - 1]=pop(line[li - 1], k); //맨 위의 인자 pop => 해당 프렛 손 떼기
result++;//시행 +1
}
else if (line[li - 1][k] < pr) { //맨 위에 저장된 인자 값이 작을 경우
top_arr[li - 1] = push(line[li - 1], pr, k); //프렛 인자를 새롭게 push => 해당 프렛 잡기
result++; //시행+1
break; //더 이상 반복되지 않도록 탈출
}
else break; //만약 이미 해당 프렛 인자가 있을 경우 break로 탈출
}
 
}
printf("%d", result); //결과값 출력
 
//동적할당 메모리 해제
for (int i = 0; i < 6; i++) {
free(line[i]);
}
free(line);
return 0;
}
 
int push(int stack[], int value, int top) { //스택에 인자 집어 넣는 함수
stack[++top] = value; //top+1 인덱스에 value값 넣기
return top; //top값 반환
}
 
int pop(int stack[], int top) { //스택 top의 인자 빼는 함수
return --top; //top-1 값 반환
}