[C언어 / 백준 - 2841번] 외계인의 기타 연주 (스택)

 

www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

문제

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

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

출력

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

예제 입력 1 복사

7 15

1 5

2 3

2 5

2 7

2 4

1 5

1 3

예제 출력 1 복사

9

 

해당하는 줄에 따라 비교해야 하는 스택문제이다.

줄은 1~6번까지 존재하므로 stack 또한 하나의 stack이 아닌 6개의 stack이 필요한 것이다. 이것을 구조체와 배열을 함께 사용하여 해결하였다. 해당되는 줄이 오게 되면 그 줄에서의 stack을 확인하여 추가하는 경우, 손을 떼야하는 경우, 그대로 둬도 되는 경우를 생각하여 코드를 작성하였다.

 

예제를 예시로 보면,

처음에 1 5가 오고 1번 줄의 stack을 확인한다 -> 1번 stack은 현재 비어있는 상태이므로 그냥 stack에 푸쉬해준다.

그 다음 2 3도 마찬가지로 2번 줄의 stack은 비어있는 걸 확인하고 푸쉬해준다 -> 다음 2 5를 보면 2번 stack은 비어있지 않으므로 top을 확인한다 -> top은 2 3이므로 프렛의 값이 5보다 작다 -> 따라서 굳이 손을 뗄 필요가 없으므로 바로 푸쉬만 해주는 횟수를 세어준다 / 만약 top의 프렛이 내가 연주해야하는 프렛보다 큰 값이라면 pop을 해주어야하고 top을 최신화해주어 계속해서 확인해준다 이에 따른 횟수도 추가로 세어주어야한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 203
typedef struct road {
	int rope;
	int pret;
}road;

typedef struct Intstack {
	int size[7];
	road stack[7][MAX_SIZE];
}Intstack;

Intstack s;

void Init_Stack(Intstack* s) {
	for (int i = 0; i < 7; i++) {
		s->size[i] = 0;
	}
}

int Push(Intstack* s, int x, int y) {
	if(s->size[x] + 1 > MAX_SIZE) return 0;
	road temp;
	temp.rope = x;
	temp.pret = y;
	s->stack[x][s->size[x]++] = temp;
	return 1;
}

road Pop(Intstack* s,int place) {
	return s->stack[place][--s->size[place]];
}

road top(Intstack* s,int place) {
	return s->stack[place][s->size[place] - 1];
}

int Size(Intstack* s,int place) {
	return s->size[place];
}
/*
기타는 1번~6번 줄이 존재, 각 줄은 P개의 프렛으로 나누어져 있다.
프렛의 번호도 1번부터 P번까지 나누어져 있다.
만약, 어떤 줄의 프렛을 여러 개 누르고 있다면 가장 높은 프렛의 음이 발생

- 손가락으로 프렛을 한 번 눌,거나 떼는 것을 손가락을 한 번 움직였다고 한다.
어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 횟수를 구하는 프로그램
*/
int N, P;
int cnt;

void Solve(road* rd) {
	for (int i = 0; i < N; i++) {
		if (Size(&s, rd[i].rope) == 0) {
			Push(&s, rd[i].rope, rd[i].pret);
			cnt++;
		}
		else {
			road temp = top(&s, rd[i].rope);
			while (temp.pret > rd[i].pret) {
				Pop(&s, rd[i].rope);
				temp = top(&s, rd[i].rope);
				cnt++; 
			}
			if (temp.pret == rd[i].pret) {
				continue;
			}
			Push(&s, rd[i].rope, rd[i].pret);
			cnt++;
		}
	}
}


int main() {
	Init_Stack(&s);
	scanf("%d %d", &N, &P);
	road* rd = (road*)malloc(sizeof(road) * N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &rd[i].rope, &rd[i].pret);
	}
	Solve(rd);
	printf("%d", cnt);
	free(rd);

	return 0;
}