[25439] 죄수들의 도전

난이도: Diamond III

 

태그

• Ad-Hoc
• Constructive
• Divide and Conquer
• Dynamic Programming

 

풀이

1. 서브태스크 1만 해보자. (\( N \le 500, m \le 500 \))

간단합니다. 1번 죄수는 \( 0 \)을 보고, A를 본 뒤, A에 있는 수를 그대로 적으면 됩니다.

2번 죄수는 \( A \)를 읽고, B를 본 뒤, B에 있는 수와 칠판에 적힌 수 (A)를 비교해서 답을 출력하면 됩니다.

 

2. 좀 더 효율적으로 비교할 수 없을까? (\( m = 32 \))

한 번에 수 전체를 비교하는 대신, 앞에서부터 한 자리씩 비교해나가는 방식을 생각해볼 수 있습니다.

 

예로, 2169와 2187을 비교한다 해봅시다.

그럼, 처음으로 오는 죄수는 0을 보고, A를 읽고, 2169의 1000의 자리인 2를 적습니다.

그 다음으로 오는 죄수는 2가 적힌 걸 보고, B를 읽고, 2187의 1000의 자리인 2와 같음을 본 뒤, 다시 0을 적습니다.

이는 다음 죄수에게 100의 자리를 읽으라는 표시이죠.

그러고 다음 죄수는 0을 보고, ...어라?

 

아무래도 수만 적으면 통신에 문제가 생기는 것 같습니다.

그러니, 수랑 위치를 같이 써봅시다.

 

다시 2169와 2187을 비교한다면,

처음으로 오는 죄수는 0을 보고, A를 읽고, 2169의 1000의 자리라는 의미인 (1000, 2)를 적습니다.

// 실제로는 수 하나를 적어야 하지만, 어차피 pair ↔ int 간의 mapping이 가능하니 문제 없습니다.

다음으로 오는 죄수는 (1000, 2)를 보고, B를 읽고, 1000의 자리가 같음을 본 뒤, (100, -1)을 적습니다.

다음으로 오는 죄수는 (100, -1)을 보고, A를 읽고, 2169의 100의 자리를 의미하는 (100, 1)을 적습니다.

다음으로 오는 죄수는 (100, 1)을 보고, B를 읽고, 100의 자리가 같으니 (10, -1)을 적습니다.

다음은 (10, -1)을 보고, A를 읽고, (10, 6)을 적습니다.

다음은 (10, 6)을 보고, B를 읽고, 6 < 8이기 때문에 A를 답으로 판단하고 종료합니다.

 

죄수가 하는 행동은 간단합니다. (d, x)가 주어지면, x = -1일 때는 A를 읽고, x를 A의 d번째 자리로 업데이트합니다.

x ≠ -1이라면, B를 읽고, 적혀있던 x와 비교한 뒤, 같다면 (d-1, -1)을 적고, 다르다면 비교 결과를 토대로 답을 냅니다.

 

이 때 사용하는 상태의 개수는 아래와 같습니다.

10진법에서 가능한 자리수의 위치는 \( 1, 10, 100, 1000 \)으로 4가지입니다.

각각에 대해 가능한 값은 \( 0 \)부터 \( 9 \)까지, 그리고 아직 읽지 않음의 \( -1 \)까지 총 11가지죠.

즉, \( m = 44 \)라는 결론이 나옵니다.

 

\( m = 44 \)는 아무래도 너무 크니, 진법을 바꿔봅시다.

아래는 다양한 진법에 대한 결과입니다.

• 2진법: \( [1, 2, 4, 8, \ldots, 2^12 = 4096] \times [-1, 0, 1] \) → \( m = 13 \times 3 = 39 \)
• 3진법: \( [1, 3, 9, 27, \ldots 3^7 = 2187] \times [-1, 0, 1, 2] \) → \( m = 8 \times 4 = 32 \)
• 4진법: \( [1, 4, 16, \ldots, 4^6 = 4096] \times [-1, 0, 1, 2, 3] \) → \( m = 7 \times 5 = 35 \)
• 5진법: \( [1, 5, 25, 125, 625, 3125] \times [-1, 0, 1, 2, 3, 4] \) → \( m = 6 \times 6 = 36 \)
• ...

 

3진법을 사용한 결과 \( m = 32 \)가 여기서는 최적이니, 3진법을 사용하여 문제를 풀면 됩니다.

 

3. 좀 더 효율적으로 비교할 수 없을까? (\( m = 24 \))

[2]에서의 작동 방법을 유심히 살펴봅시다.

 

A = 2169, B = 2187일 때:

처음으로 오는 죄수는 0을 보고, A를 읽고, 2169의 1000의 자리라는 의미인 (1000, 2)를 적습니다.

다음으로 오는 죄수는 (1000, 2)를 보고, B를 읽고, 1000의 자리가 같음을 본 뒤, (100, -1)을 적습니다.

...

 

뭔가 이상함이 느껴지나요?

굳이 (100, -1)으로 갈 필요 없이, B의 100의 자리수인 (100, 1)을 바로 넣어줄 수 있을텐데 말이죠.

대신에, 여는 순서를 "1000의 자리는 A / 100의 자리는 B / 10의 자리는 A / 1의 자리는 B" 이런 식으로 정해줘야겠죠.

 

이렇게 하면, (d, -1)의 상태가 필요없어집니다. 바로바로 d의 자리를 넣어주기 때문이죠.

 

이제 이걸 토대로 다시 필요한 상태의 수를, 각 진법별로 계산해봅시다.

• 2진법: \( [1, 2, 4, 8, \ldots, 2^12 = 4096] \times [0, 1] \) → \( m = 13 \times 2 = 26 \)
• 3진법: \( [1, 3, 9, 27, \ldots 3^7 = 2187] \times [0, 1, 2] \) → \( m = 8 \times 3 = 24 \)
• 4진법: \( [1, 4, 16, \ldots, 4^6 = 4096] \times [0, 1, 2, 3] \) → \( m = 7 \times 4 = 28 \)
• 5진법: \( [1, 5, 25, 125, 625, 3125] \times [0, 1, 2, 3, 4] \) → \( m = 6 \times 5 = 30 \)
• ...

 

3진법, \( m = 24 \)까지 줄인 것을 볼 수 있습니다.

 

4. 좀 더 효율적으로 비교할 수 없을까? (\( m = 22 \))

앞에서 한 일들에 비하면 간단한 작업입니다.

 

(3진수로 나타냈을 때) A = 120221, B = 120222라고 해봅시다.

그럼, 243의 자리부터 비교를 시작해서 마지막 1의 자리까지 내려오게 됩니다.

 

앞에서부터 비교를 하기 때문에, 1의 자리까지 내려왔다는 의미는 앞부분은 다 동일하다는 말이 됩니다.

그런데, A와 B가 다르다는 조건 때문에 여기서 재밌는 짓을 해볼 수 있습니다.

 

만약 이 시점에서 B를 열었다고 해봅시다.

그럼, 여기서 알 수 있는 건 A = 12022?이고 B = 120222라는 정보입니다.

그런데 A ≠ B이기 때문에, A를 열어보지 않아도 이미 A가 더 작거나 같다는 걸 알 수 있습니다.

// ?에 들어갈 수 있는 건 0 또는 1밖에 안 남는데, 둘 다 2보다 작죠.

비슷하게, 만약 1의 자리가 0이었다면 반대쪽을 열지 않아도 지금 연 게 더 작다는 걸 알 수 있습니다.

 

이는 무엇을 의미하냐면, 이 두 경우에 해당하는 상태인 (1, 0)과 (1, 2)를 지워도 문제없다는 소리입니다.

(1, 0)과 (1, 2)가 하는 일이 "반대쪽을 열어보고 결정하라"는 명령을 내리는 건데,

그 명령을 내리기 전에 결정을 내려버렸으니 굳이 명령을 남길 필요가 없겠죠.

 

이렇게 하면 아까 계산했던 \( m = 24 \)에서 상태 2개를 빼서 \( m = 22 \)로 줄일 수 있습니다.

 

5. 좀 더 효율적으로 비교할 수 없을까? (\( m = 21 \))

굳이 마지막 스텝에서만 지워야 할까요?

 

저걸 좀 더 일반화하자면, A를 열었는데 이 값이 범위의 최소이거나 범위의 최대라면

추가적인 판별 없이 바로 답을 알아낼 수 있다는 의미입니다.

 

그러니까, 우리가 알아낸 범위가 [1, 5000]이었다면

A를 열고 나서 아래와 같은 선택을 할 수 있습니다.

• A = 1: 자명히 A < B입니다.
• A = 5000: 자명히 A > B입니다.
• 남은 4998가지 경우는 (3진수를 가정하면) 3등분해서, [2, 1667], [2668, 3333], [3334, 4999]로 해결하면 됩니다.

 

조금 더 생각해봅시다.

현재 보고 있는 구간을 \( N \)이라고 하고, 이를 \( b \)등분로 나눠서 나온 각 구간의 길이가 \( M \)이라면

\( N = b \cdot M + 2 \)라는 관계식을 세울 수 있습니다.

// + 2는 우리가 빼는 1과 5000의 경우고, 나머지는 길이 \( M \)의 구간 \( b \)개입니다.

이 때 사용되는 상태의 수는 구간의 개수인 \( b \)개가 되겠네요.

 

또한, 우리는 \( N \le 2 \)일 때는 추가적인 상태 없이 판별할 수 있다는 것도 알고 있습니다.

그럼, \( b \)진법을 사용할 때 몇 개의 상태를 가지고 있어야 \( N = 5000 \)까지 다 판별할 수 있는 지 확인할 수 있겠죠.

 

역시, 다양한 진법에서 돌려봅시다.

• 2진법 (\( N = 2M + 2 \)): \( 2 \rightarrow 6 \rightarrow 14 \rightarrow 30 \rightarrow 62 \rightarrow 126 \rightarrow 254 \rightarrow 510 \rightarrow 1022 \rightarrow 2046 \rightarrow 4094 \rightarrow 8190 \), \( m = 2 \times 11 = 22 \)
• 3진법 (\( N = 3M + 2 \)): \( 2 \rightarrow 8 \rightarrow 26 \rightarrow 80 \rightarrow 242 \rightarrow 728 \rightarrow 2186 \rightarrow 6560 \), \( m = 3 \times 7 = 21 \)
• 4진법 (\( N = 4M + 2 \)): \( 2 \rightarrow 10 \rightarrow 42 \rightarrow 170 \rightarrow 682 \rightarrow 2730 \rightarrow 10922 \), \( m = 4 \times 6 = 24 \)
• 5진법 (\( N = 5M + 2 \)): \( 2 \rightarrow 12 \rightarrow 62 \rightarrow 312 \rightarrow 1562 \rightarrow 7812 \), \( m = 5 \times 5 = 25 \)
• ...

 

최적은 3진법, \( m = 21 \)이 되겠네요.

 

6. 좀 더 효율적으로 비교할 수 없을까? (\( m = 20 \))

잠깐만요. 굳이 하나의 진법으로 통일해야 할까요?

 

지금까지 \( b \)진법으로 설명하긴 했지만, 사실상 진법이 가지고 있는 의미는 수를 적당히 나눠주는 것 외에는 없습니다.

그러니, 특정 시점까지는 3등분하다가 그 후로는 2등분으로 갈아타는 등의 경우가 가능하겠죠.

 

하지만 이렇게 하면 검사해봐야 할 경우가 많아집니다.

다행히도, 이 계산을 우리가 해줘야 할 필요는 없죠.

 

아래와 같은 DP를 세워봅시다.

\( dp_{N} \) = \( N \)개의 수를 판별하기 위해 필요한 상태의 최소 개수

 

초항은 \( dp_{1} = dp_{2} = 0 \)입니다.

전파는 \( dp_{kM + 2} \leftarrow dp_{M} + k \)로 해주면 됩니다.

// \( dp_{M} \)에서 \( dp_{kM + 2} \)로 전파하는 방식입니다.

 

이렇게 돌리고, \( dp_{5000} \)을 확인해보면 정확히 \( 20 \)이 나옵니다.

적어도 우리가 가는 길이 틀린 길은 아니었다는 의미겠네요.

 

하지만 \( 20 \)개로 가능하다는 사실 자체는 별로 중요하지 않습니다.

우리가 필요로 하는 건 "어떤 방식으로 채워야" \( 20 \)개가 되는가이죠.

 

다행히도, 이건 DP 역추적으로 구해줄 수 있습니다.

 

저의 경우는, \( [1, 2, 2, 2, 3, 3, 3, 4] \)라는 결과가 나왔습니다.

구간의 길이로 적자면, \( [2, 4, 10, 22, 46, 140, 422, 1268, 5074] \)가 되겠죠.

 

이제 이를 토대로, \( 5074 \)에서부터 시작해서 시작과 끝을 잘라주고

\( 4, 3, 3, 3, 2, 2, 2, 1 \)등분해주면서 내려가면 \( m = 20 \)으로 풀 수 있습니다.

 

7. 구현 디테일

\( [st, ed] \)를 들면서 재귀로 구현하다보면 채워지지 않는 칸이 생기게 됩니다.

 

이 칸들은 우리가 직접 빼주는 "최소/최대인 경우"일 때만 발생하는데,

해결 방법은 "최소/최대"를 손으로 채워넣을 때

더 깊은 깊이에 있는 상태들도 같이 채워넣어주면 됩니다.

 

8. 코드

const int X = 5074;
 
const int arr[12] = {0, 4, 3, 3, 3, 2, 2, 2, 1, 0};
const int pos[12] = {0, 1, 5, 8, 11, 14, 16, 18, 20, 21};
const int len[12] = {0, 5074, 1268, 422, 140, 46, 22, 10, 4, 2};
vector< vector<int> > res( 21, vector<int>(X+1) );
 
void dnc(int dep, int idx, int st, int ed){
    res[idx][ed] = -(dep&1) - 1; res[idx][st] = -3 - res[idx][ed];
    for (int b = pos[dep]; b <= 20; b++){
        if (res[b][0] == res[idx][0]){
            res[b][st] = res[idx][st]; res[b][ed] = res[idx][ed];
        }
        else{
            res[b][ed] = res[idx][st]; res[b][st] = res[idx][ed];
        }
    }
    st += 1; ed -= 1;
    if (st > ed){ return; }
    for (int b = 0; b < arr[dep]; b++){
        int bi = b + pos[dep];
        int p1 = st + b*len[dep+1]; int p2 = p1 + len[dep+1];
        for (int p = st; p < p1; p++){ res[bi][p] = res[idx][ed+1]; }
        for (int p = p1; p < p2; p++){ res[idx][p] = bi; }
        for (int p = p2; p <= ed; p++){ res[bi][p] = res[idx][st-1]; }
        dnc(dep+1, bi, p1, p2-1);
    }
}
 
vector< vector<int> > devise_strategy(int N){
    res[0][0] = 0;
    int p1 = 1; for (int i = 1; i <= 8; i++){
        int p2 = p1 + arr[i];
        for (int p = p1; p < p2; p++){ res[p][0] = i&1; }
        p1 = p2;
    }
    dnc(1, 0, 1, X);
    for (int i = 0; i <= 20; i++){ res[i].resize(N+1); }
    /*for (int i = 0; i <= 20; i++){
        if (i < 10){ cout << ' ' << i << " | "; }
        else{ cout << i << " | "; }
        for (int j = 0; j <= N; j++){
            if (j == 0){ cout << (res[i][j]==0 ? 'A' : 'B') << "   "; }
            else{
                if (res[i][j] < 0){ cout << ' ' << (res[i][j]==-1 ? 'A' : 'B') << ' '; }
                else if (res[i][j] < 10){ cout << ' ' << res[i][j] << ' '; }
                else{ cout << res[i][j] << ' '; }
            }
        }
        cout << endl;
    }
    cout << endl;*/
    return res;
}