[BOJ #15889] 호 안에 수류탄이야!!

문제 설명

문제 링크
N명의 전우들이 1열로 서있고 각 전우들은 자신의 사거리 안에서 좌우로 수류탄을 던질 수 있다.

0번 위치에 있는 욱제부터 전우들에게 수류탄을 던져 결국 맨 오른쪽의 전우가 수류탄을 행사용 폭죽 더미에 놓아야 하는 문제

모든 전우가 항상 최선을 다해 최적의 방법으로 수류탄을 행사용 폭죽 더미에 놓으려고 노력한다.

알고리즘

맨 왼쪽 전우(욱제)에서 맨 오른쪽 전우에게 수류탄을 전달할 수 있는가의 문제이기 때문에 수류탄을 왼쪽으로 던질 경우는 생각하지 않아도 된다.

그러므로 i 번째 전우가 k 번째 전우에게 수류탄을 전달하려면 (i < k)

1. i 번째 전우가 직접 k 번째 전우에게 던진다.
2. i 번째 전우가 j 번째 전우(i+1 < j < k-1)에게 던진 후 j 번째 전우가 k 번째 전우에게 던진다.
   의 2가지 경우가 존재한다.

즉, 맨 왼쪽에서 시작해 오른쪽으로 스위핑하면서 다음을 생각하면 된다.
i 번째 전우의 위치를 지나 i+1 번째 전우에게 수류탄을 전달하는 경우는

1. i 번째 전우가 직접 i+1번째 전우에게 던지는 경우
2. j 번째 전우(j < i 라 하자)가 i+1 번째 전우에게 던지는 경우

두 가지이고 이를 코드로 구현하면 다음과 같다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N;
int pos[30000];
int range[30000];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // init
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> pos[i];
    for (int i = 0; i < N-1; ++i)
        cin >> range[i];


    int remainingDis = 0;
    bool guardhouse = false;
    for (int i = 0; i < N; ++i) {
        if (remainingDis - pos[i] < 0) { guardhouse = true; break; }
        remainingDis = max(remainingDis, pos[i] + range[i]);
    }

    if (guardhouse) cout << "엄마 나 전역 늦어질 것 같아" << '\n';
    else cout << "권병장님, 중대장님이 찾으십니다" << '\n';
}

느낀 점...

독해 문제... 조건들이 지문 곳곳에 숨어 있기 때문에(욱제가 수류탄을 던지기 시작, 욱제의 좌표는 항상 0) 처음에 무의식적으로 풀고 다시 검증하는 과정에서 이게 왜 정상적으로 작동하는지 오랫동안 생각하게 되었다.