[4159] 알래스카

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

4159번: 알래스카

<문제>

0에서 1422까지 가는 경우를 먼저 생각해보자.

(1422+1)*2번을 한마일씩 이동하듯 반복문을 돌린다, 현재 마일에 충전소가 있다면 무조건 충전하는것으로 간주하고,

하나의 루프가 끝나면 남은 전기를 1 감소시켜준다. 물론, 남은 전기가 없어지면 바로 IMPOSSIBLE이 답이된다.

1422에서 0으로 가는 경우엔, 위를 동일하지만, 순서만 반대로 바꿔주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (1) {
        cin >> n;
        if (n == 0) break;
        vector<int> v(n);
        int i;
        for (i = 0; i < n; i++) cin >> v[i];
        sort(v.begin(), v.end());
        int cur = 200, idx = 0;
        bool flag = true;
        for (i = 0; i <= 1422; i++, cur--) {
            if (v[idx] == i) {
                cur = 200;
                idx++;
            }
            if (cur < 0) {
                flag = false;
                goto findAns;
            }
        }
        idx = v.size() - 1;
        for (i = 1422; i >= 0; i--, cur--) {
            if (v[idx] == i) {
                cur = 200;
                idx--;
            }
            if (cur < 0) {
                flag = false;
                goto findAns;
            }
        }
    findAns:
        flag ? cout << "POSSIBLE\n" : cout << "IMPOSSIBLE\n";
    }
    return 0;
}