레이저 타워 디펜스 (백준 2493 : 탑)

2493번: 탑 (acmicpc.net)

2493번: 탑

문제를 보는 순간, 완전탐색으로 풀면 되겠네!

 

했지만, 고르든 등급의 백준 문제는 그런 추잡한 시도는 용납하지 않는다. 

그럼 어떤 식으로 풀어야 할까.

 

- 대전략:

 탑 높이 리스트는 tower로 저장하고, 우선 체크리스트( check = [] ) 를 만들자.

또한, tower에 대해 for i in range(N)으로 왼쪽부터 ptr(포인터)가 시작하도록 하자. 

 

또한, ptr 시작은 0 으로 하자. 왜 why.

문제를 보면 왼쪽으로 빔을 쏘는데, tower[0] 의 왼쪽은 아무것도 없는 공허의 세계이기 때문이다.

 

그럼 for문을 시작해볼까. 

 

ptr은 현재 높이보다 낮을 때, 갱신되도록한다. 왜 why

ptr은 이 탑이 쏜 레이저가 어느 탑(의 위치)에 맞는지를 표시하는 것이기 때문이다. 

 

그렇기때문에 첫번째 타워를 보자. 타워의 높이는 6이고 왼쪽에는 아무것도 없다.

그래서 ptr (0) 을 남겨주는 것이다.

 

다음 탑은 9이고, 타워 높이가 전보다 올라갔기 때문에 ptr 0을 표시한다. 

 

하지만, 다음 탑은 5이기 때문에 ptr을 전 타워의 위치(2)로 갱신해주고, 그 ptr(2)를 남긴다. 

 

또 다음 탑은 7이기 때문에 ptr를 갱신하지 않고 현재 ptr(2)를 남긴다. 

하지만 다음 높이는 4이기 때문에 ptr을 4로 갱신하고 남겨준다.

 

그럼 이제 코드를 짜보자. 

import sys

N = int(sys.stdin.readline())

tower = list(map(int,sys.stdin.readline().split()))
check = []
ptr = 0

check.append(ptr)


for i in range(1, N):
    if tower[i-1] > tower[i]:
        ptr = i
        check.append(ptr)
    else:
        check.append(ptr)

print(check)

역시나 틀렸습니다가 나왔다.

이제 반례를 찾아보자.

 

첫번째 반례는 다음과 같다.

5
7 2 8 11 123123

 

정답은 0 1 0 0 0이지만, 내 출력은 0, 1, 1, 1, 1이 나온다.

 

아하! 만약 ptr의 타워 높이 보다 더 높은 탑이 나왔을 때를 넣지 않았던 것이다.

그러면 어떻게 해야할까.

 

ptr를 2차원 리스트로 만들어서 높이와 인덱스를 갱신하는 방법이 있지 않을까.

ptr = [h(탑의 높이), idx(탑의 위치)] 로 넣어준다.

 

그림으로 다시 설명하겠다.

위 그림에서 대부분의 상황이 나와있다고 생각한다.

우선 ptr의 정의부터 시작하자.

 

ptr 은 포인터를 나타낸다. 현재 탑이 왼쪽으로 레이저를 쏘면 어느 탑에 맞을지를 나타내는 포인터다.

시작할 때는 빈 공간이므로 아무것도 없다.

 

check 는 리스트로, tower[i]가 쏘는 레이저가 몇번째 탑(탑의 idx + 1)에 맞는지를 표시한다.

결과로 check를 제출할 것이다.

 

그리고 1번 탑이 나왔을 때, 1번탑이 쏘는 곳은 -당연히- 아무 탑에도 안맞으므로 check[0] = 0 이다.

 

이제 1번 탑의 운명에 대해 생각해보자.

 

2번탑이 1번탑보다 낮다면 1번탑이 레이저를 맞을 것이기 때문에 1번탑의 인덱스를 표시해야한다.

하지만, 2번탑이 1번탑보다 크다면? 

그러면 불쌍한 1번탑에게 레이저를 쏘아주는 친구는 아무도 없을 것이다. 그 경우를 생각해 1번탑의 높이도 표시해야한다. (왜 필요한 지는 조금 있다가 더 상세하게 설명하겠다.)

 

그렇기 때문에 ptr = [탑 높이, 탑 위치] 인 것이다. 

 

그럼 한번 2번탑을 봐보자. 2번탑의 높이에 따라 1번탑의 운명이 바뀔 것이다.

 

2번탑은 1번탑보다 높이가 낮다.

 

그렇다면 우리는 1번탑의 높이와 위치를 기억해줘야 한다. 

ptr = [h1, i] 가 된다. tower 리스트 상의 1번탑의 위치는 0 이고, i는 2번째 탑의 위치를 말하는 거지만, 출력에 탑의 위치가 아니라 몇번째 탑인지를 나타내야하기 때문에 ptr = [ h1(1의 높이) , i - 1 + 1]이 되어서 i가 된다. 유의하자.

 

i번째 탑이 i-1번째 탑보다 낮을 경우의 코드는 다음과 같다.

    # 같거나 내려갈 때, 
    else:
        ptr.append([tower[i-1], i])
        if len(ptr) > 0:
            check.append(ptr[-1][1])
        else:
            check.append(0)

탑[i]이 탑[i-1]보다 낮으면 탑[i]가 쏘는 레이저는 무조건 바로 전의 탑이 맞기 때문에 check에는 ptr[-1][1]. 즉, i-1를 넣어주게 된다.

 

3번째탑도 2번째 탑보다 낮으니 ptr에 기록해줘야한다.

그렇다면 현재 ptr에는 [h1, 1], [h2, 2]가 기록되어있다. 자, 다음으로 가보자.

 

 

드디어 탑이 높아지는 경우가 왔다.

4번째 탑은 3번째 탑보다 높다.

이제 ptr에는 [h1, 1], [h2, 2], [h3, 3] 이 기록되어 있다.

 

그렇다면 4번째 탑이 쏘는 빔은 3번째 탑에 맞지 않게 된다. 

그러면 어느 탑이 맞게 될 것인가? 이 날을 위해 우리는 ptr을 기록했다.

다음 식을 봐보자.

    # 탑의 높이가 높아진다면.
    if tower[i-1] < tower[i]:
        judge(tower[i], i)
        if len(ptr) > 0:
            check.append(ptr[-1][1])
        else:
            check.append(0)

# 탑 높이가 올라갔을 때, ptr의 탑과 현재 탑을 비교함.
def judge(h, idx):
    while len(ptr) > 0:
        if ptr[-1][0] >= h:
            break
        else:
            ptr.pop()

전의 탑보다 현재 탑이 높을 경우, judge를 실행한다. 이 함수는 현재 탑이 쏘는 레이저가 ptr에 기록되어있는 탑 중에 어느 탑에 맞을 건지를 판별한다.

 

judge는 ptr에 기록이 남아있을 때 계속 반복된다. 

그리고 ptr[-1][0] >= h 인 경우. 즉, ptr의 가장 최근에 기록한 탑(현재로선 3번)이 현재 탑보다 높거나 같다면 (레이저가 이 탑에 맞는다면) 중단된다.

 

만약 가장 최근의 탑이 현재탑보다 낮다면, 가장 최근의 탑에는 이제 아무도 레이저를 쏴주지 않을 것이다. 그렇기 때문에 삭제시킨다. 

 

현재 ptr은 [h1, 1], [h2, 2], [h3, 3]이다.

h3은 h4 보다 낮기 때문에 [h3, 3]은 삭제시킨다. (pop)

 

그 다음은 h2이다. h2는 다행히도 h4와 같기 때문에 남겨둔다.

 

그리고 ptr에 아직 기록이 있다면 (현재로선 [h1, 1], [h2, 2]가 있다.) check에 ptr에 써져있는 마지막 탑의 idx를 기록한다.

 

 

여기서, "왜 현재 탑의 ptr은 기록하지 않나요?" 라고 할 수 있는데, 만약 이 다음의 탑이 현재 탑보다 높다면 ptr을 기록해도 의미가 없다. 또, 다음 다음 탑의 높이가 더 높다면, 현재 탑과 다음 탑의 높이는 의미가 없기 때문에 ptr을 기록하는 것은 탑의 높이가 낮아질 때 실행한다.

 

 

이제, 5번째 탑을 보자. 5번째 탑은 2번째 탑보다 높기 때문에 ptr에서 2번째 탑의 기록을 지운다.

6번째 탑은 1번째 탑보다도 높이가 높기 때문에 왼쪽으로 쏘면 아무도 안 맞을 것이다.

그렇기에 1번째 탑의 ptr도 지워줘야 한다.

 

이런 식으로 진행해서 check를 반환하면 정답이 나온다.

 

 

이것이 탑의 풀이이다.

전체 코드는 다음과 같다.

 

import sys
sys.stdin = open("input.txt", "r")

N = int(sys.stdin.readline())

tower = list(map(int,sys.stdin.readline().split()))
check = []
ptr = [] # [[탑 높이, 탑 위치]]

check.append(0)

# 탑 높이가 올라갔을 때, ptr의 탑과 현재 탑을 비교함.
def judge(h, idx):
    while len(ptr) > 0:
        if ptr[-1][0] >= h:
            break
        else:
            ptr.pop()
    


for i in range(1, N):
    if tower[i-1] < tower[i]:
        judge(tower[i], i)
        if len(ptr) > 0:
            check.append(ptr[-1][1])
        else:
            check.append(0)
    # 같거나 내려갈 때, 
    else:
        ptr.append([tower[i-1], i])
        if len(ptr) > 0:
            check.append(ptr[-1][1])
        else:
            check.append(0)


print(*check)

 

그럼 다음 시간에~