백준 4159번 [알래스카](C++) -yes6686- 티스토리

백준 문제 풀이: 4159 [알래스카]

---

문제 링크: https://www.acmicpc.net/problem/4159

문제 설명:

알래스카 지역에서는 최대 200 마일의 범위 안에서 다음 주유소를 찾아야 합니다. 주어진 주유소의 위치를 바탕으로 정방향과 역방향 모두에서 가능한지 확인하여 "POSSIBLE" 또는 "IMPOSSIBLE"을 출력하세요. 시작점은 0 마일이며, 마지막 주유소에서 1422 마일까지의 거리도 고려해야 합니다.

---

문제 해결 코드

// 백준 4159 - 알래스카
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector stations(n);
        for (int i = 0; i < n; i++) {
            cin >> stations[i];
        }

        // 정렬
        sort(stations.begin(), stations.end());

        // 1422 마일에서 마지막 주유소로 왕복 가능해야 하므로 1422를 추가
        stations.push_back(1422);

        bool possible = true;
        for (int i = 1; i < stations.size(); i++) {
            // 인접한 두 주유소 사이의 거리가 200 마일을 초과하면 불가능
            if (stations[i] - stations[i - 1] > 200) {
                possible = false;
                break;
            }
        }

        // 역방향 검증: 마지막 주유소에서 1422로 왕복 가능 여부 확인
        if (possible && 1422 - stations[n - 1] > 100) {
            possible = false;
        }

        cout << (possible ? "POSSIBLE" : "IMPOSSIBLE") << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 정렬 후 인접한 주유소 간의 거리 차이를 확인하여 200 마일 이하인지 검증합니다.
• 구현 세부사항:
  • 정렬된 배열을 순회하면서 거리 차이가 200 마일을 초과하는 경우를 탐지합니다.
  • 마지막 주유소에서 역방향으로 100 마일 이내에 출발점(1422)이 있어야 합니다.
• 시간 복잡도 분석:
  • 정렬: O(n log n)
  • 거리 검증: O(n)
  • 총 시간 복잡도: O(n log n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!