cdjs의 코딩 공부방

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

1. 문제

- x축 위에 점들이 N개($n \leq 100,000$) 있음

- 초기에 i번째 점에서 시작해서, 모든 N개의 점을 순회할 수 있는지 확인해야 함

- 단, 이동 시에는 이전에 이동했던 거리의 최소 2배 이상 이동해야 함

- 각 N개의 점에 대해서, 각 점에서 출발하여 모든 N개의 점을 순회할 수 있으면 YES를, 없으면 NO를 출력함.

1-1. 힌트

힌트 1

힌트 2

힌트 3

2. 문제 관찰 과정

우선, 문제의 조건과 시간 제한을 살펴보자.

모든 테스트케이스에서의 N의 범위가 $N \leq 1,000,000$이므로, 각 $N$개의 점에 대해서 200번 이하의 연산을 진행해야 시간 초과가 나지 않는다(대략 1억회의 연산을 1초라 가정함). 하지만 정답을 YES로 출력하는 점에 대해서는 필연적으로 해당 점에서부터 모든 $N$개의 점을 순회해야 하므로 시간복잡도가 $O(N^2)$이 된다. 즉, 문제에 숨겨진 또 다른 조건을 찾아야 한다는 뜻이다.

문제에서 이동 거리는 최소 1이고, 다음에 이동할 때는 이전 거리의 2배는 이동해야 한다고 제시하였다. 그런데, $2^{21}=2,097,152$이기 때문에 초기에 아무리 조금 움직였더라도 추가로 20번만 이동하더라도 이미 x축의 범위인 $10^{-6} \leq a_i \leq 10^6$에 의해 더 이상 다음 점으로의 이동이 불가능하다. 즉, 어차피 각 테스트케이스에서 이동 횟수가 20보다 크다면 정답은 무조건 NO가 된다. 이 경우, 움직인 횟수를 $M$이라 하면 시간복잡도가 테스트케이스 당 $O(M^2)$이 되어도 $T{M}^2 = 22,050,000$이므로 시간 안에 풀이가 가능하다.

그러나 $N$개의 점에 대하여, $i$번째 이동에 $N-i$개의 점으로 이동이 가능하므로 완전 탐색 시뮬레이션을 돌리게 되면 시간 복잡도가 $N!$이 되어 시간 안에 풀이가 불가능하다. 어떻게 $O(N!)$의 시간복잡도를 $O(N^2)$으로 바꿀 수 있을까?

3. 풀이

위 문제 풀이의 가장 중요한 아이디어는 다른 점을 건너뛰고 이동하면 안 된다는 것이다.

예를 들어, $A < B < C $인 세 점에서 $A$에서 $C$로 이동한 경우를 생각해 보자.

점 $A$와 점$C$ 사이의 거리가 $x$라고 두면, 다음으로 이동할 수 있는 거리는 최소 $2x$이다.

이 때, 점 $C$에서 오른쪽으로 $y (2x \leq y)$만큼 이동하면 그 다음으로 이동할 수 있는 위치는 $C+2y$ 이상, $C-2y$이하이므로 결코 점 $B$에 도달할 수 없다.

마찬가지로 점$C$에서 왼쪽으로 $y$만큼 이동하는 경우에서도 결코 점 $B$로 도달할 수 없다.

이렇듯, 다른 점을 건너뛰고 이동하면 필연적으로 그 사이에 있는 점으로는 도달할 수 없다는 점을 확인할 수 있다.

하지만 이 사실을 알아내더라도 좌/우로 모두 이동하는 것을 완전 탐색으로 시뮬레이션을 돌리게 되면 시간복잡도는 여전히 $O(2^N)$으로, 제한 시간 내에 풀이가 불가능하다.

좌/우 중 어느 것을 고르는 것이 최적일지 판단은 어떻게 할 수 있을까?

문제를 간단히 하기 위해, $A < B < C$ 인 세 점 중 점 $B$ 에서 시작하는 경우를 예시로 들어 보자.

$A$와 $B$ 사이의 거리를 $x$, $B$와 $C$ 사이의 거리를 $y$라고 하자.

점$B$에서 점$A$로 이동하는 경우 다음으로 이동할 수 있는 위치는 $A+2x$ 이상 $A-2x$ 이하이다.

이 때, $y<x$인 경우 $A-2x < C < A+2x$이므로 절대로 점$C$로 이동할 수 없다.

즉, 좌/우 중 한 곳을 선택하는 경우, 무조건 짧은 거리만을 선택해야 한다는 것이다.

위 아이디어들을 종합하면, 다음과 같은 풀이가 도출된다.

"$N$개의 점에 대해, 항상 좌/우 중에서 가장 가까운 거리에 있는 점으로 이동한다(이 때, 좌/우의 거리가 동일한 경우에는 좌/우 모두 이동해 본다). 그렇게 이동하면서 다음에 이동할 점이 결코 도달 불가능한 점에 있을 경우 답은 NO이고, 끝까지 $N$번째 점으로 이동했다면 답은 YES이다."

이것을 코드로 그대로 구현해 보자.

4. 코드

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int n;
vector<ll> a;

bool solve(int x, int r, int l, ll gap) {
    if (l>=0 && r<n) {
        if (a[r]-a[x]<a[x]-a[l]) {
            if (gap>a[r]-a[x])    return false;
            return solve(r, r+1, l, (a[r]-a[x])*2);
        }
        else if (a[r]-a[x]>a[x]-a[l]){
            if (gap>a[x]-a[l])    return false;
            return solve(l, r, l-1, (a[x]-a[l])*2);
        }
        else {
            return (solve(l, r, l-1, (a[x]-a[l])*2) || solve(r, r+1, l, (a[r]-a[x])*2));
        }
    }
    else if (l>=0) {
        if (gap>a[x]-a[l])    return false;
        return solve(l, r, l-1, (a[x]-a[l])*2);
    }
    else if (r<n) {
        if (gap>a[r]-a[x])    return false;
        return solve(r, r+1, l, (a[r]-a[x])*2);
    }
    else {
        return true;
    }
}

int main()
{
    int t;
    int r, l;
    ll gap;
    
    cin >> t;
    while (t--) {
        int x=0;
        scanf("%d",&n);
        a = vector<ll>(n, 0);
        
        for (int i=0; i<n; i++) {
            scanf("%lld",&a[i]);
        }
        
        for (int i=0; i<n; i++) {
            gap=1234567890;
            r=i+1;
            l=i-1;

            if (l>=0)    gap = min(gap, a[i]-a[l]);
            if (r<n)    gap = min(gap, a[r]-a[i]);
            
            if (solve(i, r, l, gap))    printf("YES\n");
            else    printf("NO\n");
        }
    }
}

5. 여담

위 풀이에서 최악의 케이스는 좌우가 동일한게 계속 반복되서 나오는 경우인데, 제한 조건 안에서 아무리 좌우가 동일하게 반복되어봤자 그렇게까지 많은 케이스를 방문하지 않게 되므로, 시간 내에 충분히 풀이가 가능하다.

난이도 기여를 보니까 의도된 풀이는 DP인 것 같은데, 나중에 그 풀이도 살펴봐야겠다.