12. 1141 : 불쾌한 날

원본 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=50&sfl=wr_subject&stx=%EB%B6%88%EC%BE%8C%ED%95%9C+%EB%82%A0&sop=and

JUNGOL | 불쾌한 날 > 문제은행

문제풀이 :

#include <stdio.h>
//스택을 이용하여 문제 풀기
#define MAX 80050
unsigned int stack[MAX];    //stack 생성
int s_p = 0;    //스택 포인터
long long sum = 0;  //sum
void push(int data) {
        stack[++s_p] = data;
        sum += s_p - 1;
}
 
int main() {
    int N;  //입력되는 수 N<=80000
    int temp;
    scanf("%d", &N);
    //처음 입력되는 수는 Stack에 일단 PUSH.
    scanf("%d", &temp);
    push(temp);
    for (int i = 1; i < N; i++) {
        scanf("%d", &temp);
        if (stack[s_p] > temp) {
            //새로 입력 받은 값이 stack에 st_pt 포인터가 가리키는 곳 밑에 값보다 작다면 PUSH.
            push(temp);
        }
        else if(stack[s_p] <= temp){
            //새로 입력 받은 값이 stack에 st_pt 포인터가 가리키는 곳 밑에 값보다 크거나 같다면 POP.
            s_p--;
            //계속 POP할 것인지 ?
            while (1) {
                if (stack[s_p] > temp) {
                    //큰 값이 있을 때 까지 탐색.. 아니면 pop
                    push(temp);
                    break;
                }
                else {
                    --s_p;
                    //전부 다 POP 되면 break
                    if (s_p == 0) {
                        push(temp);
                        break;
                    }
                }
            }
        }
    }
 
    printf("%lld\n", sum);
    return 0;
}

내가 볼 수 있는 소들의 합 = 나를 보고 있는 소들의 합

나를 볼 수 있는 소들만 stack에 남겨둔다