[백준] 4159번 알래스카 C++ 코드

코드

#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

int n, a[1500];

void FASTIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    FASTIO();
    while(1) {
        cin >> n;
        fill(a, a + 1500, 0);
        if(!n) break;
        for(int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            a[tmp] = 1;
        }
        int can = 200; // 충전
        int dist = 0; // 거리
        bool ok = false; // 가는 것을 확인하는 변수
        bool ok2 = false; // 오는 것을 확인하는 변수
        while(can--) {
            dist++;
            if(a[dist]) can = 200;
            if(dist >= 1422) {
            	// 델타 정션 도착
                ok = true;
                break;
            }
        }
        if(ok) {
            while(can--) {
                dist--;
                if(a[dist]) can = 200;
                if(dist <= 0) {
                	// 더슨 크릭 도착
                    ok2 = true;
                    break;
                }
            }
        }
        // 둘 다 갈 수 있는 경우만 POSSIBLE
        cout << (ok&&ok2 ? "POSSIBLE\n" : "IMPOSSIBLE\n");
    }
    return 0;
}

풀이

거리가 1422라서 브루트포스로 확인했다. 다 확인해도 3000번 미만일 것이기 때문에... 그런데 정렬하고 거리가 200이고 마지막 충전소가 1322 이상인지 판정하면 된다는 풀이를 보고 더 열심히 해야겠다는 생각을 하게 됐다.