백준_15889_호 안에 수류탄이야!! (python)

# 그리디 알고리즘

# n의 범위가 현저히 작았다면 dfs 풀이도 가능한데 n의 범위가 너무 크다.

 

★ 풀이

이 문제의 주 목적은 욱제부터 공을 던지기 시작해서 마지막 사람이 받을 수 있냐 없냐이다. 결국 욱제부터 공을 던져서 욱제 오른쪽 사람들이 받으면서 마지막 사람한테 전해주면 된다. 그럴라면 어떻게 해야할까? 일단 최대 사거리로 던진다. 그리고 바로 오른쪽 사람이 받을 수 있다면 오른쪽 사람이 최대로 던진다. 그 과정에서 바로 전에 사람보다 더 멀리 던진다면 값을 갱신시켜주고 그것이 아니라면 값을 유지한다. 이 과정을 마지막 사람까지 반복해주면 된다.

 

★ 코드

import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int,input().split()))
if n == 1:
    print("권병장님, 중대장님이 찾으십니다")
else:
    temp = list(map(int,input().split()))
    st = [data[0] + temp[0]]
    for i in range(n-1):
        if data[i] <= st[-1]:
            if data[i] + temp[i] >= st[-1]:
                st.pop()
                st.append(data[i] + temp[i])
        else:
            break    
    if data[n-1] <= st[-1]:
        print("권병장님, 중대장님이 찾으십니다")
    else:
        print("엄마 나 전역 늦어질 것 같아")

 

 

★ 회고

 이런 문제는 이제 쉭쉭~ 훅훅~ 풀어야 하는데 너무 고민을 했다...... 최근에 ps를 쉰 것도 있지만 예상보다 더 많이 고민했다. 다시 한번 감을 찾아보자