여기를 클릭해 주세요.
문제 링크
https://www.acmicpc.net/problem/2841
문제 요약
기타는 총 6개의 줄로 이루어져 있으며 높은 플랫을 누르면서 낮은 플랫을 동시에 누르고 연주가 가능하지만
낮은 플랫을 눌러 연주를 해야하는데 이 때 높은 플랫이 눌려 있으면 안된다.
외계인이 연주할 곡의 음 순서가 들어올 때 손을 움직이는 횟수를 최소화 하고 싶다
문제 풀이
외계인이 각각의 손을 움직여야 할지 말아야 할지 모든 경우를 탐색해 보는것은 불가능하다.
하지만 잘 생각해 본다면 그 순간에 선택을 해야할지 그리디하게 결정할 수 있다.
우선 한개의 줄에 \(x \lt y\lt z\) 인 음이 있다고 생각을 해 보자.
이 때 연주하는 경우의 수는 크게 두가지로 나눠서 생각을 해볼 수 있다.
1. 높은 음에서 낮은 음으로 가는 경우
2. 낮은 음에서 높은 음으로 가는 경우
1번과 같은 경우 현재 누르고 있는 음이 \(y\), \(z\)라고 하고 다음 누르려고 하는 음이 \(x\)라고 한다면 \(y\), \(z\)의 음에서 손을 떼야함이 자명하다.
2번과 같은 경우 조금 생각을 해 본다면 현재 누르고 있는 음이 \(x\), \(y\)라고 할 때 \(z\)를 연주할려고 한다면 굳이 \(x\), \(y\)에서 손을 땔 필요가 없다는 것을 알 수 있다. 언젠가는 1번과 같은 경우가 올것이고 이 때 손을 움직이는것이 최선의 경우다.
이것을 여섯개의 줄로 확장시킨다 하더라도 각각의 줄이 모두 독립적이기 때문에 6개의 스택을 사용해 해결할 수 있다.
소스 코드
더보기
#include <stdio.h> #include <stack> using namespace std; int n, m, x, y, ans; stack<int> s[7]; int main() { scanf("%d%d", &n, &m); while (n--) { scanf("%d%d", &x, &y); while (!s[x].empty() && s[x].top() > y) { ++ans; s[x].pop(); } if (s[x].empty() || s[x].top() != y) { s[x].push(y); ++ans; } } printf("%d\n", ans); }