[BOJ] 2439 탑

문제: https://www.acmicpc.net/problem/2493

 2009년 초등부 지역본선 4번, 고등부 지역본선 2번 문제이다. 그만큼 난이도도 매우 쉬운 스택 문제기는 한데 처음 보면 스택 문제가 아니라고 생각할 수도 있을 거라 생각한다. 풀이는 다음과 같다.

 이 문제를 푸는 가장 적절한 알고리즘은, 왼쪽부터 탑의 높이를 차례대로 보면서 스택의 맨 위와 비교해서, 스택의 수가 더 클 때까지 pop하고 그 때 숫자를 출력하는 것이다. 굉장히 단순하기 짝이 없지만 제대로 동작하는 알고리즘이다.

 대략적으로라도 증명을 해보자.

1. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 왼쪽에서 부딪히는 경우는 없다.

원래 부딪혀야 하는 것보다 왼쪽에서 부딪혔다고 가정해 보자. 스택에서 pop을 할 때 원래 부딪혀야 하는 곳이 스택 내에 존재한다면 왼쪽에 있는 탑보다는 항상 먼저 나오므로 원래 부딪혀야 하는 곳이 스택에 들어 있으면 왼쪽에 부딪힐 수는 없다. 따라서 원래 부딪혀야 하는 곳은 스택에 들어 있을 수 없는데, 원래 부딪혀야 하는 곳이 스택에 없으려면 원래 부딪혀야 하는 곳의 탑이 스택에 push된 이후에 그것보다 더 큰 탑이 삽입되었다는 이야기가 되고, 이는 레이저가 원래 부딪혀야 하는 곳에 애초에 맞을 수가 없었다는 것을 뜻한다. 모순.

2. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 오른쪽에서 부딪히는 경우는 없다.

원래 부딪혀야 하는 것보다 오른쪽에서 부딪혔다고 가정해 보자. 그렇다면 원래 부딪혀야 하는 곳보다 오른쪽에 현재 스택에 넣어질 탑보다 높이가 높은 탑이 존재한다는 얘기이다. 그런데 레이저가 그 새로운 탑에 부딪히려면 그 새로운 탑은 현재 스택에 넣어질 탑보다 먼저 스택에 삽입되었어야 하고, 스택에 들어있는 원소는 항상 맨 위에서부터 증가하므로(이는 자명하니까 증명 생략) 새로운 탑에 부딫히려면 스택의 증가때문에 원래 부딪혀야 하는 탑보다 높이가 작아야 한다. 모순이다.

따라서 이 알고리즘을 사용했을 때 레이저가 엉뚱한 곳에서 맞는 경우는 있을 수 없고, 따라서 알고리즘이 성립한다.

그럼에도 불구하고 증명없이 직관적으로 프로그램이 구현 가능한 정도의 난이도이다. 1.75/5?

#include <cstdio>
#include <stack>
#include <algorithm>
#define INF (2000000000)
 
using namespace std;
 
int main()
{
    int n;
    stack<pair<int,int> > S;
 
    scanf("%d",&n);
    S.push(make_pair(INF,0));
 
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        while(S.top().first<t) S.pop();
        printf("%d ",S.top().second);
        S.push(make_pair(t,i));
    }
    return 0;
}