[알고리즘] 백준 3015 c++

문제 링크

3015번: 오아시스 재결합

틀린이유

• 키가 큰 애들이 남아서 작은 애들을 볼 수 있는 게 아니라
• A와 B 사이에 (A && B) 보다 키 큰 사람이 없어야 함
• 문제 이해 & 해석 잘못함
  • why? 내가 틀렸다는 거 받아들이기 쉽지 않았음..
  • 틀렸으니까 틀린 거다!!! 다른 사람이 틀린 거 찾듯이 내 반례를 찾자 😣
• 반례)
  • in) n=3 / 3 2 1 → out) 2
  • 위의 예시 나는 3으로 생각했음..
  • 중간에 키 큰 사람 없어야 쌍이 되므로 out이 2가 나와야했음!!

#include <iostream>
#include <stack>

using namespace std;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  long long ans = 0;
  int n;
  cin >> n;

  stack<int> S;
  while (n--) {
    int height;
    cin >> height;
    ans += S.size();  
    while (!S.empty() && S.top() < height) S.pop();
    S.push(height);
  }
  cout << ans;

  return 0;
}

문제 분석

문제

• N명의 사람들이 한 줄로 서 있다
• 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키 큰 사람이 없어야 한다
• 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하여라.

입력

• 줄 서 있는 사람의 수 N : 1≤ N ≤ 500,000
• 각 사람의 키 나노미터 단위 : h < 2^31

해결방안

• N이 ≤ 500,000이니까 O(NlogN) 혹은 그 아래로 풀어야 함
• stack 내림차순으로 정렬
• S.top() < height 했을 경우 h 앞에 있는 키 같은 경우의 쌍 셀 수 없고,
  S.top() <= height 했을 경우에도 남아있어야하는 키 같은 경우를 pop 해버리니까
• 키 같은 경우를 저장하는 second 필요! → pair로 저장해야한다!

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  stack<pair<int, int>> S;
  long long ans = 0;
  while (n--) {
    int h;
    cin >> h;
    int cnt = 1;
    while (!S.empty() && S.top().X <= h) {
      ans += S.top().Y;
      if (S.top().X == h) cnt += S.top().Y;
      S.pop();
    }
    if (!S.empty()) ans++;
    S.push({h, cnt});
  }
  cout << ans;
}