[파이썬/python] 백준 1863번 스카이라인 쉬운거

import sys
from collections import Counter
N = int(sys.stdin.readline())
skyline = list()
for i in range(N):
    A, B = map(int, sys.stdin.readline().split())
    tup = (A, B)
    tup = list(tup)
    skyline.append(tup)
count = 0
index = 1

# 사실 지금 생각해보니 튜플로 저장할 필요가 없음
# x좌표는 어차피 순서대로 입력돼서 필요 없는데 왜 저장했지
# 아무튼 바꾸기 귀찮으니까 걍 커밋함
for i in skyline:
    if i[1] == 0:
        index += 1
        continue
    if i == skyline[N - 1]:
        count += 1
        break
    for n in skyline[index:]:
        if i[1] > n[1]:
            count += 1
            break
        elif i[1] == n[1]:
            n[1] = 0
        if n == skyline[N-1]:
            count += 1
    index += 1

print(count)

그리디 알고리즘

문제를 제대로 이해하는 것이 중요합니다.

재미있는 문제였습니다. 

알고리즘은 다음과 같습니다.

 

가로로 탐색하며:

    1. 현재 건물 높이보다 낮은 높이가 나오면 끊어주고 count += 1 합니다.

    2. 현재 건물 높이와 같은 높이가 나오면 높이를 0으로 만들고 continue 합니다.

    3. 높이가 0이면 무조건 continue합니다.

 

사실 어려운 문제는 아니므로 곰곰히 생각해보시면 위의 알고리즘을 이해하실 수 있겠습니다.

코드가 더러운데, 굳이 입력의 A는 저장할 필요 없습니다. 어차피 순차적으로 입력됩니다..