[수학/그리디] 백준 14659 한조서열정리하고옴ㅋㅋ - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14659번: 한조서열정리하고옴ㅋㅋ

 

 

 

2. 문제 풀이

 뒤에 자신보다 낮은 봉우리가 있으면 죽일 수 있습니다. 한 사람이 최대 몇 명을 죽일 수 있는지 구해야 합니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 직관적으로 가장 높은 봉우리 뒤에 낮은 봉우리가 몇 개 있는지 세보면 됩니다. 앞에서부터 탐색하며, 현재 가장 높은 봉우리를 기준으로 뒤에 몇 명이나 있는지 셉니다. 끝에 도달하면, 가장 많은 킬 수를 출력합니다.

 

 

 

3. 코드

# 입력
N = int(input())
high = list(map(int, input().split()))

# 그리디
high_max = 0
cnt = 0
res = 0
for i in high:
    # 더 높은 봉우리 만나면 갱신
    if i > high_max:
        high_max = i
        cnt = 0

    # 더 낮은 봉우리면 Kill
    if i < high_max:
        cnt += 1
    res = max(res, cnt)
print(res)

 가장 높은 봉우리라도, 뒤에 사람이 별로 없으면 가장 많은 킬을 내지 못합니다. 그렇기 때문에 그리디 알고리즘으로 '현재' 가장 높은 봉우리를 기준으로 매번 몇 명이나 죽일 수 있는지 cnt로 셉니다.

 res에는 현재까지의 최다 킬 수를 저장합니다.