[백준]: 2841번: 외계인의 기타연주 / Stack & pair

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

이 문제를 잘 이해하면, 예제가 잘 이해될 것이다.

7 15 

1 5 => 1회 

2 3 => 1회 

2 5 => 1회 

2 7 => 1회 

2 4 => 3회 => 7번, 5번 플렛 뗌 4번 플렛을 누름

1 5 => 1회 => 눌려있음. (cnt 제외)

1 3 => 2회 => 5번 플렛 떼고 3번 플렛 누름

또한, 총 6개의 줄이있기떄문에, stack 6개를 생성하는 것보다 stack 1개에 pair<first,second>로 묶어서 정리하는것이 효율적이다.

#include<iostream>

using namespace std;

#include<stack>

stack <pair<int, int>> s[8];

int n,p,cnt;

int main()

{

cin >> n>>p;

pair <int, int> p;

for (int i = 0; i < n; i++)

{

cin >> p.first >> p.second;

if (s[p.first].empty())                        //비어 있다면 넣고,

{

s[p.first].push(p);

cnt++;

}

if (s[p.first].top().second < p.second) {        //숫자가 클 경우 (ex) 1 3 / 1 5 순으로 들어오면 3<5)

s[p.first].push(p);

cnt++;

}

else if (s[p.first].top().second == p.second) {

continue;

}

else

{

while (!s[p.first].empty() && s[p.first].top().second > p.second) {  // 숫자가 작을 경우 ex) 1 5 / 1 3 순으로 들어올 경우)

s[p.first].pop();

cnt++;

}

if(!s[p.first].empty())        // s[p.first].empty()유무 파악후, 비어있지않으면 같지않은지를 비교해야한다. 같으면 넣지못하니까

{

if (s[p.first].top().second != p.second)

{

s[p.first].push(p);

cnt++;

}

}

else if (s[p.first].empty())

{

s[p.first].push(p);

cnt++;

}

}

}

cout << cnt << "\n";

return 0;

}