[백준] 2493 탑

2493번: 탑

fast io 미적용

문제 확인

 

배열 인덱스를 따라가면서 만족하는 인덱스를 찾는 방식으로 풀 수 있습니다.

스택을 활용하여 문제를 풀어도 비슷한 결과가 나옵니다.

 

풀이

 

2가지 경우로 나눕니다.

1. 전에 입력받은 탑의 크기가 현재 탑 보다 큰 경우 : 현재 탑이 발사한 레이저 신호를 수신한 탑은 i - 1이 됩니다.
2. 현재 탑이 작은 경우 : i - 1부터 수신 가능한 탑을 찾아 내려갑니다.

i - 1 번째 탑이 발사한 레이저 신호를 어느 탑이 수신하였는가(dist[i-1])를 보고 수신한 탑이 현재 탑보다 큰 경우 해당 탑을 고르면 됩니다. 만약 해당 탑(dist[i-1]) 또한 현재 탑 보다 작은 경우 이러한 과정을 큰 탑이 나오거나 0에 도달할 때까지 반복합니다.

 

코드

#include <iostream>
 
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    int ary[500001], dist[500001];
 
    ary[0] = 0x7fffffff;
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> ary[i];
 
 
    for (int i = 2; i <= n; i++) {
        if (ary[i - 1] < ary[i]) {
            int t = i - 1;
            while (ary[t] < ary[i])
                t = dist[t];
            dist[i] = t;
        }
        else {
            dist[i] = i - 1;
        }
    }
 
    for (int i = 1; i <= n; i++)
        cout << dist[i] << ' ';
}