[Silver III] 알래스카-4159

[문제 위치]

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

[문제 풀이]

이 문제는 그리디 + 구현을 통해 해결하는 문제다.

 

고속도로 길이와 충전소 간의 거리 조건을 점검해, 정방향과 역방향 모두 순차적으로 점검하며 가능한지 확인하면 된다.

 

아래는 이를 구현한 코드이다.

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

#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FAST_IO;
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        
        const int TOTAL = 1422;  // 더슨 크릭 ↔ 델타 정션까지 거리
        const int MAX_DIST = 200;  // 한 번 충전 시 최대 이동 거리
        
        bool ok = true;
        // 정방향: 맨 앞 0 마일에서 시작
        // 더슨 크릭(0) → 첫 충전소, 충전소 간 거리, 마지막 충전소 → 델타 정션 모두 MAX_DIST 이하인지
        // 더슨 크릭은 위치 0으로 가정
        if (a.size() > 0) {
            if (a[0] > MAX_DIST) ok = false;
        }
        for (int i = 1; i < n && ok; ++i) {
            if (a[i] - a[i-1] > MAX_DIST) {
                ok = false;
            }
        }
        // 마지막 충전소 → 델타 정션
        if (ok) {
            if (TOTAL - a[n-1] > MAX_DIST) {
                ok = false;
            }
        }
        
        // 역방향: 델타 정션 → 돌아올 때도 검토
        // 델타 정션에서 출발하여 다시 더슨 크릭까지 올 때
        // 델타 정션에서 가장 마지막 충전소까지, 즉 (TOTAL - last) 거리도 이동 가능해야 하고
        // 그 거리 이외에도 돌아가는 경로 확보를 위해 본래 최대거리가 200이므로
        // (TOTAL - a[n-1]) * 2 ≤ MAX_DIST 이어야 함
        if (ok) {
            if ((TOTAL - a[n-1]) * 2 > MAX_DIST) {
                ok = false;
            }
        }
        
        cout << (ok ? "POSSIBLE" : "IMPOSSIBLE") << "\n";
    }
    return 0;
}