BOJ17608 막대기

문제

BOJ17608 막대기
브론즈II | 백준 17608 | Python3 파이썬 풀이

알고리즘

한 쪽에서 보았을 때 볼 수 있는 막대를 세어보자.

일단 맨 처음 막대는 무조건 볼 수 있다.

어떤 막대를 볼 수 있는 조건은 무엇일까? 막대를 1번부터 $N$개까지 세어갈 때, 어떤 막대의 순서가 $c$번째이고, 그 막대의 길이가 $h_c$라면,

위 상태에서 $c$번째 막대는 볼 수 없다. 4번 막대가 더 크기 때문에 가려진다.

이를 공식으로 나타내면 어떤 막대를 볼 수 있는 조건은
$h_c > h_i, i=\{x|1<=x<c\}$이다. 즉, 그 막대 앞쪽에 더 큰 막대가 없어야 한다.

즉 해당 막대를 볼 수 있는지 체크하려면 그 막대 앞에 더 큰 막대가 있는지 검사한다.

이를 방향을 오름차순으로 생각하면, 어떤 $i$에 대해 ($i=\{x|1<=x<c\}$) 높이가 가장 큰 막대를 $h_{max}$라고 할 때 어떤 막대 $c$의 높이 $h_c$가 $h_{max}$보다 크다면, $h_{max} >= h_i, i=\{x|1<=x<c\}$가 성립하고, 이로 인해 $h_c > h_i, i=\{x|1<=x<c\}$ 공식이 성립한다.

즉 간단하게 말해서, 어떤 막대가 보이는 조건은 그 막대 앞에 그 막대보다 큰 막대가 없어야 한다.

코드

import sys

input = sys.stdin.readline

N = int(input())

heights = [int(input()) for _ in range(N)][::-1]

# 가장 큰 높이 저장
m = heights[0]
# 볼 수 있는 막대 수
# 맨 앞 막대는 무조건 볼 수 있다.
count = 1

for height in heights:
	# 현재 막대가 이전 모든 막대보다 크면
    if height > m:
    	# 현재 막대를 볼 수 있다.
        count += 1
        # 가장 큰 막대 높이 수정
        m = height

print(count)

결과