[백준 BOJ][stack] 3015 오아시스 재결합

3015_오아시스 재결합

링크

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

 

풀이

 

우선 스택을 사용해서 사람들을 내림차순으로 나열하고(같은 수도 포함), 이전보다 더 큰 수가 들어오면 스택을 지워나가며 ans를 구합니다.

다 끝나고 스택에 남아있는 내림차순 사람들을 지워나가며(1명 남기고) ans에 더해줍니다.

 

지울 때가 중요한데요. 내림차순 도중 더 큰 게 들어오면

이렇게 지워질 때 자신의 양쪽을 볼 수 있으니 ans에 2씩 더해주면 됩니다. 하지만 자신이 맨 왼쪽이었다면 왼쪽을 볼 수 없으니 ans에 1을 더해주면 됩니다.

 

그리고 같을 때가 문제인데요. 같은 키를 가진 사람들끼리 볼 수 있는 인원 + 같은 키를 가진 사람들이 볼 수 있는 왼쪽 오른쪽 사람을 더해주면 됩니다.

 

가운데 3명만 고려했을 때, 자기들끼리 3명 볼 수 있고, 3명이 왼쪽 오른쪽 각각 볼 수 있어서 6명 볼 수 있습니다. 총 9명 볼 수 있죠.

일반화해서 가운데 n명을 고려했을 때, 자기들끼리 1~(n-1) 합만큼 볼 수 있고, n명이 왼쪽 오른쪽 각각 볼 수 있어서 n*2명 볼 수 있습니다. (자신이 맨 왼쪽일 경우 n명 볼 수 있겠죠)

 

마지막 내림차순에서는 내림차순이면서 오른쪽으로 더 안 들어오기 때문에 왼쪽만 고려하면 됩니다.

이때 한 명을 남겨야 하는데요. 뒤에서부터 계산하면서 이미 그 사람이 본 것까지 계산되기 때문입니다. 1명 남을 때까지 뒤에서부터 올라오면서 스택을 내림차순으로 쌓을 때 맨 왼쪽 고려한 것처럼 이번에는 자신이 맨 오른쪽인 것을 고려해 코드를 짜면 됩니다.

 

코드

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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

//3015_오아시스 재결합 #include <cstdio> #include <stack> #include <algorithm> using namespace std;   int n, h[500001], a[500001], tmp, cnt; int n1, n2; long long int ans; stack<int> stk;   int main() {     scanf("%d", &n);       for (int i = 0; i <n; ++i) {         scanf("%d", &h[i]);     }       for (int i = 0; i< n; ++i) {         while (true) {             if (!stk.empty()) tmp = h[stk.top()];             else tmp = -1;               if (tmp < h[i] && tmp != -1) {                 n1 = h[stk.top()];                 stk.pop();                 if (!stk.empty()) {                     n2 = h[stk.top()];                 }                 else {                     n2 = -1;                 }                   if (n1 == n2) {    //연속된 키의 사람들끼리 본 쌍 카운트 (1 ~ n-1)의 합                     cnt++;                     ans += cnt;                 }                   else {                     if (cnt) {    //연속된 키들의 마무리                         ++cnt;                         if (stk.empty())            //stk.empty()는 현재가 제일 왼쪽임을 의미                             ans += cnt, cnt = 0;    //그래서 오른쪽만 카운트                         else                             ans += cnt * 2, cnt = 0;    //아니라면 왼쪽 오른쪽 다 카운트                     }                     else {    //불연속 키                         if (stk.empty())                              ans++;                         else {                             ans += 2;                         }                     }                 }             }             else {                 stk.push(i);                 break;             }         }     }       while (stk.size() != 1) {    //오름차순의 남은 사람들         n1 = h[stk.top()];         stk.pop();         n2 = h[stk.top()];           if (n1 == n2) {             cnt++;             ans += cnt;         }           else {             if (cnt) ans += ++cnt, cnt = 0;    //왼쪽만 카운트             else ans++;         }     }       printf("%lld\n", ans);       return 0; } Colored by Color Scripter

cs