줄별로 스택 관리하면서 top을 보고 관리를 하면 된다.
본문에 나와있는 것 처럼 3번줄의 5,7번 프렛을 누르고 있을 때 2번 프렛을 연주하려면 5,7번을 다 떼는 것 말고는 방법이 없기때문.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> #include <stack> using namespace std; int n, p, a, b, ans; stack<int> s[6]; int main() { scanf("%d%d", &n, &p); while (n--) { scanf("%d%d", &a, &b); a--; if (s[a].empty()) ans++, s[a].push(b); else if (s[a].top() == b) continue; else if (s[a].top() < b) { ans++; s[a].push(b); } else if (s[a].top() > b) { while (s[a].size() && s[a].top() > b) s[a].pop(), ans++; if (s[a].size() && s[a].top() == b) continue; s[a].push(b), ans++; } } printf("%d\n", ans); return 0; } | cs |