문제 링크 : https://www.acmicpc.net/problem/2841
2841번: 외계인의 기타 연주
첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수
www.acmicpc.net
풀이
이전의 스택 문제들과 비슷하게 접근하여 풀었다.
기타의 줄이 6줄이므로 6개의 stack을 가지는 배열을 선언하였다.
아무 프렛도 안 누른 상태를 가정하여 0을 스택에 넣고 시작했는데, 이 덕분에 스택이 비어 오류가 발생하는 것을 걱정하지 않아도 된다.
#include <iostream>
#include <stack>
using namespace std;
stack<int> A[6];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0; i < 6; i++) A[i].push(0); // 아무것도 안 누른 상태를 넣어준다.
int n, p;
cin >> n >> p;
int cnt = 0;
while(n--){
int tn, tp;
cin >> tn >> tp;
while(1){
if(A[tn-1].top() <= tp) break; // 이번에 누른 프렛이 top보다 크거나 같다면 break
A[tn-1].pop(); // 크거나 같은 것이 나올 때까지 pop
cnt++; // 손을 뗐으므로 cnt 1 추가
}
if(A[tn-1].top() != tp){
A[tn-1].push(tp); // 누른 프렛 스택에 추가
cnt++; // 프렛을 눌렀으므로 cnt 1 추가
}
}
cout << cnt;
}
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
(C++) 백준 10866번 - 덱 (1) | 2023.03.21 |
---|---|
(C++) 백준 10845번 - 큐 (0) | 2023.03.21 |
(C++) 백준 2493번 - 탑 (0) | 2023.03.17 |
(C++) 백준 1406번 - 에디터 (0) | 2023.03.16 |
(C++) 백준 5397번 - 키로거 (0) | 2023.03.16 |