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

문제

백준 15889번 호 안에 수류탄이야!! https://www.acmicpc.net/problem/15889

15889번: 호 안에 수류탄이야!!

코드

#include<iostream>
#include<algorithm>
using namespace std;
int pos[30003], dist[30003];
bool visited[30003];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> pos[i];
	if (n == 1) {
		cout << "권병장님, 중대장님이 찾으십니다";
		return 0;
	}
	for (int i = 0; i < n - 1; i++) {
		cin >> dist[i];

		int next = dist[i] + pos[i];
		int idx = i+1;
		if (next < pos[idx] && !visited[idx]) {
			cout << "엄마 나 전역 늦어질 것 같아";
			return 0;
		}
		while (next >= pos[idx]) {
			visited[idx] = true;
			idx++;
		}
	}

	if (visited[n - 1]) cout << "권병장님, 중대장님이 찾으십니다";
	else cout << "엄마 나 전역 늦어질 것 같아";

}

풀이방법

n이 1이면 자기 자신이 끝번이므로 무조건 성공한다. 그게 아니라면, for문을 돌리며 다음으로 갈 수 있는 최대위치를 계산해서 그 거리까지의 visited를 true로 바꿔준다. 다음 위치까지 가는 방법이 존재하지 않으면 실패한다. for문이 끝나고 n-1번째에 갈 수 있다면, 성공이고 아니면 실패다.

고민과정

처음에 그냥 무작정 벡터로 받아와서 sort하고 다음 사람한테 보낼 수 있는지 여부만 체크했다가 틀렸다. 여러 사람 건너서 보낼 수도 있고, 같은 위치에 여러 사람이 있을 수도 있다는 조건을 간과했다. 너무 오랜만에 알고리즘 문제를 풀었더니 뇌가 굳었나보다ㅠ

조건에 <=를 써야하는데 <를 썼다가 99%에서 실패하는 진귀한 경험도 해봤다............ㅎ 다시는 하고싶지 않은 경험이다.

그리고 비주얼스튜디오를 업데이트 안하고 그냥 돌렸더니 자꾸 말도안되는 오류가 나서 돌아버리는 줄 알았다. 놀랍게도 업데이트하고 났더니 잘만 실행됐다. 아무리 귀찮아도 업데이트는 일단 하고 보는거로,,,

dist[]배열은 굳이 안써도 될거같긴 하다. 솔직히 고치기 귀찮았다. 그리고 엄밀하게 따지면 배열 이름을 visited가 아니라 visitable로 해야하지 않을까 싶다.