BOJ 17608棒

3640 ワード
インプリメンテーション データ構造 スタック テキストリンク

質問する


BOJ 17608棒
青銅II|白駿17608|Python 3 Python池

アルゴリズム#アルゴリズム#



片側から見たときに見える棒を数えます.
まず最初の棒はきっと
どの棒が見える条件は何ですか?1からNNN個までの本数を数える場合、ある本数の順番がcccで、その本数の長さがhch chcであれば、

上記の状態では、cccの2本目のレバーは見えません.4番がもっと大きいので止められました.
式として表すと、次の条件が表示されます.
hc>hi,i={x∣1<=xhi,i={x∣1<=xつまり、レバーが見えるかどうかを確認するには、レバーの前にもっと大きなレバーがあるかどうかを確認します.
この方向を昇順と見なすと、あるiiii(i=x1<=x\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\<<<<=hi,i={x∣1<=xhi,i={x∣1<=xhi,i={x∣1<=xつまり、簡単に言えば、ある棒が見ている条件は、その前に大きな棒があるべきではないということです.

コード#コード#

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)

結果


UITableView
pta 1099. Build A Binary Search Tree (30)