[C/C++] 정올 1141. 불쾌한 날

문제는 다음과 같습니다.

 

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

 

이 문제를 풀기 위해서는 모든 입력을 배열에 넣고 할 수도 있지만, 사실 큰 소가 들어오면, 그 사이에 있는 작은 소들은 더 이상 앞의 소들을 볼 수 없기 때문에 계속 입력을 유지할 필요가 없습니다.

 

Cows

예를 들면,

현재 소들의 키가 다음과 같이 되어 있다면,

13 10 9 6 4

여기에 8 의 소가 오면, 6과 4의 키를 가지는 소들은 더 이상 유지할 필요가 없습니다. 그래서 그 소들을 없애면서 볼 수 있는 소들의 숫자 합을 늘린 후 다음과 같이 배열을 유지하면 됩니다.

13 10 9 8

이렇게 하면 소들의 배열을 최소화할 수 있습니다.

 

제가 작성한 소스입니다.  프로그램은 참고용으로만 해주세요.

#include <stdio.h>

int main()
{
    int cows[80000];
    int n;
    int cn = 0;
    unsigned sum = 0;

    scanf("%d", &n);

    for( int i = 0 ; i < n ; i++ )
    {
        int hi;
        scanf("%d", &hi);
        while( cn > 0 && cows[cn-1] <= hi ) cn--;
        sum += cn;
        cows[cn++] = hi;
    }
    printf("%u\n", sum);
}