호 안에 수류탄이야!!
"호 안에 수류탄!!"
대한건아 욱제는 수류탄 투척 훈련을 받고 있다. 욱제를 필두로, 훈련장에는 욱제를 포함한 N명의 전우들이 일렬(1열 횡대)로 서 있다. 군대에 끌려온 사실에 심술이 난 욱제는 수류탄의 안전핀을 뽑아 전우에게 던졌다. 마찬가지로 심술이 난 전우들도 욱제가 던진 수류탄을 받아 전우들에게 던지기 시작했다.
이제 수류탄은 뜨거운 감자처럼 욱제와 전우들 사이를 옮겨 다닌다. 전우들은 팔 힘이 모두 다르기 때문에 수류탄을 던질 수 있는 사거리도 모두 다르다. 욱제와 전우들이 가지고 노는 훈련용 수류탄은 바닥에 떨어지기 전에는 절대 터지지 않는 특수한 수류탄이다.
욱제와 전우들은 특급 전사이기 때문에 사거리 내에 있는 누구에게나 정확히 수류탄을 던질 수 있고, 마찬가지로 정확히 날아오는 수류탄은 항상 받을 수 있다. 한 위치에 여러 명의 전우가 서 있다면 그중 아무나 받아 다음 전우에게 던질 수 있다.
누군가의 팔 힘이 모자라 수류탄이 다음 전우에게 전달되지 못하고 바닥에 떨어지는 경우도 있을 수 있다. 이때는 수류탄에서 폭죽이 터지며 불꽃놀이가 시작되고, 동시에 욱제와 전우들의 영창 생활도 시작된다.
???: "중대장은 오늘 너희에게 큰 실망을 했다"
이 게임을 중대장님이 모르게 끝마치려면 마지막 전우(왼쪽에서부터 N번째 전우)가 수류탄을 받아 조용히 행사용 폭죽 더미에 섞어놓아야 한다. 욱제와 전우들은 항상 최선을 다해 최적의 방법으로 게임을 조용히 끝마칠 수 있도록 노력한다. 과연 영창을 건 이 게임의 끝은 어디일까?
입력
제한사항 | 값 |
---|---|
전우들의 인원 수 N | 1 ≤ N ≤ 30,000 |
전우들의 좌표 | 0 ≤ 좌표 ≤ 1,000,000 |
사거리 | 0 ≤ 사거리 ≤ 1,000,000 |
출력
게임이 조용히 마무리될 수 있으면 "권병장님, 중대장님이 찾으십니다"를, 그렇지 않으면 "엄마 나 전역 늦어질 것 같아"를 출력한다.
예제 입력 1
5
0 5 10 15 100
10 5 6 100
예제 출력 1
권병장님, 중대장님이 찾으십니다
예제 입력 2
5
0 5 10 15 100
10 5 6 0
예제 출력 2
엄마 나 전역 늦어질 것 같아
def s():
n, *r = map(int, open(0).read().split()) # n: 전우 수, r: 전우 좌표 및 사거리 데이터
pos = 0 # 현재 수류탄이 도달할 수 있는 가장 먼 위치
for i in range(n - 1): # 마지막 전우 전까지 반복
pos = max(pos, r[i] + r[i + n]) # 전우 i의 위치 + 던질 수 있는 거리로 pos 갱신
if pos < r[i + 1]: # 다음 전우의 위치까지 도달하지 못하면
break # 실패 조건 발생
else:
print('권병장님, 중대장님이 찾으십니다') # 성공 시 메시지 출력
exit()
print('엄마 나 전역 늦어질 것 같아') # 실패 시 메시지 출력
스위핑이란?
스위핑은 정렬된 데이터를 순차적으로 탐색하면서 특정 조건을 만족하는 값을 계산하거나 갱신하는 기법입니다. 일반적으로 좌표나 범위를 다루는 문제에서 자주 사용되며, 효율적인 탐색이 가능합니다.
스위핑을 활용한 풀이 과정
(1) 데이터 준비
- r[i]: 전우의 좌표
- r[i + n]: 전우의 사거리
- pos: 현재 수류탄이 도달할 수 있는 최대 위치를 기록.
(2) 전우를 순차적으로 탐색
- 첫 번째 전우부터 시작하여 pos를 갱신합니다.
- 갱신식: pos = max(pos, r[i] + r[i+n])
→ 현재 전우의 위치와 사거리를 더한 값으로 도달 가능한 최대 위치를 업데이트.
(3) 조건 확인
- pos < r[i+1]일 경우, 다음 전우의 위치에 도달하지 못하므로 게임 실패.
- 이를 만족하지 않는다면 수류탄이 계속 전달됩니다.
(4) 결과 출력
- for 루프가 정상적으로 종료되면 성공 메시지를 출력합니다.
- 중간에 실패 조건이 발생하면 실패 메시지를 출력합니다.
스위핑 알고리즘이 효율적인 이유
- 시간 복잡도: $O(n)$
전우의 수만큼 순차적으로 탐색하며, 매번 위치와 사거리 값을 한 번만 갱신하므로 효율적입니다. - 공간 복잡도: $O(1)$
추가 메모리를 거의 사용하지 않고, pos 변수를 갱신하며 진행합니다.
예제 3
8
0 10 20 30 40 50 60 100
10 20 5 50 10 40 40