[파이썬/python] 백준 15889 - 호 안에 수류탄이야!!

문제

https://www.acmicpc.net/problem/15889

---

문제 설명

1. 욱제를 포함한 N명의 전우들의 좌표가 주어진다.
2. 욱제와 전우들은  사거리 내에 있는 누구에게나 수류탄을 던질 수 있다. 정확히 날아오는 수류탄은 항상 받을 수 있다.
3. 수류탄이 바닥에 떨어지지 않고 마지막 전우에게 전달해야 한다.

---

풀이

맨 처음의 사람부터 그리디하게 최대 사거리를 계산하여 마지막 전우가 받을 수 있는지 체크하면 되는 간단한 문제였다.

1. N-1번 전우까지 탐색한다.
   1. 현재 던질 수 있는 최대 사거리가 현재 전우의 좌표보다 더 길다면 최대 사거리를 현재 전우가 던질 수 있는 사거리와 현재 최대 사거리중 최대로 초기화 한다.
2. 최대 사거리가 마지막 전우의 좌표보다 크거나 같다면 "권병장님, 중대장님이 찾으십니다"를 출력한다.
   1. 그렇지 않다면 "엄마 나 전역 늦어질 것 같아"를 출력한다.

 

---

코드

import sys
input = sys.stdin.readline

N = int(input())
pos = list(map(int,input().split()))
rng = list(map(int,input().split()))

max_range = 0
for i in range(N-1):
    if max_range >= pos[i]:
        max_range = max(max_range, pos[i]+rng[i])

print("권병장님, 중대장님이 찾으십니다") if max_range >= pos[N-1] else print("엄마 나 전역 늦어질 것 같아")

---

시간복잡도

• 단순 반복문 1번으로 끝나는 문제다. 따라서 시간복잡도는 N이 최악일 때 이다. 최악일 때 $N = 30000$
• 시간복잡도는 약 $O(N) = O(3*10^4)$