[Jungol] 정올 1141 불쾌한 날(Bad Hair Day)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020

Approach

1..N까지 순차탐색으로 소들이 알 수 있는 머리 모양 개수를 구현할 수 있습니다. 

하지만 최대 N = 80,000이기 때문에 내림차순과 같이 배치되어 있다면 TLE 발생

→ Stack 처리

① 순차적으로 소들의 키 정보를 읽어갑니다.

② Stack에는 읽어온 정보보다 큰 숫자(키)만 저장합니다.

    즉, 새로 들어온 정보보다 작은 경우 pop합니다.

③ Stack에서 pop처리가 끝난 후 Stack의 크기를 반환받아 더해갑니다.

 

▶  [스택] Stack 이란? 

[스택] Stack 이란?

 

시뮬레이션

stack = [] / cow = [5 2 4 2 6 1] 

① cow = 5 (1번째 소)

    스택이 비워져 있으므로 stack = [5]

② cow = 2 (2번째 소)

    top = 5 > 2 이므로 stack = [5 2] → +1

    즉, 1번째 소의 키가 더 크므로 2번째 소의 머리를 기억합니다.

③ cow = 4 (3번째 소)

    top = 2 < 4 이므로 pop → top = 5 > 4 이므로 stack = [5 4] → +1

    2번째 소(2)는 3번째 소(4)보다 키가 작으므로 다음에 어떤 소가 있더라도 

    한마리도 기억하지 못하기에 스택에서 제거해준 것입니다.

④ cow = 2 (4번째 소)

    top = 4 > 2 이므로 stack = [5 4 2] → +2

    1, 3번째 소가 4번째 소의 머리를 알아볼 수 있습니다.

⑤ cow = 6 (5번째 소)

    top = 2 < 6 이므로 pop →  top = 4 < 6 이므로 pop → top = 5 < 6 이므로 pop

    → stack = [6] → +0

⑥ cow = 1 (6번째 소)

    top = 6 > 1 → stack = [6 1] → +1

▶ 1 + 1 + 2 + 0 + 1 = 5

---

- 소들의 정보를 순차적으로 읽어가기 때문에 cow[]에서 stack처럼 처리

- 정보를 읽을 때 기본적으로 스택이 비워져 있는 경우(top == 0)에는 바로 push한다고 볼 수 있습니다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int cows[80000];
long long sum;
int main() {
     
    int i, n; scanf("%d", &n); 
    int height, top = 0;
        
    for(i = 0; i < n ;++i) {
        scanf("%d", &height);
        while(top > 0 && cows[top-1] <= height)
            top--;
         
        sum += top;
        cows[top++] = height;
    }
 
    printf("%lld\n", sum);
}