c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q50 동시에 끝나는 모래시계

[문제]

n 개의 모래시계가 원형으로 배치되어 있다. 각 모래시계는 1분, 2분, ... .n 분을 측정할 수 있다.

모래시계를 다음과 같은 규칙으로 뒤집어 나가다고 하자.

1) 모래가 위쪽에 오도록 모래시계를 배치하고 시작 위치를 정한다.

2) 1분이 경과되면, 각 모래시계에서 1분에 해당하는 모래들이 아래로 떨어졌을 것이다.

3) 시작위치에 놓인 모래시계 번호의 개수만큼 모래시계들을 뒤집는다. (시계방향으로)

4) 원래 시작위치의 모래시계의 바로 옆(시계방향)에 놓인 모래시계를 새로운 시작위치로 정한다.

4) 1분이 경과 후, 바뀐 시작위치의 모래시계의 번호 개수만큼 모래시계를 뒤집는다.

정확한 이해를 위해서 아래 그림 참조.

[예시 1]

[예시 2]

이런 식으로 반복해 나갈 때, 순간적으로 모든 모래시계의 모래 양이 0 (즉, 모든 모래들이 모래시계의 아래쪽에 위치)이 되는 경우가 존재하는 배열의 가짓수는? 단, n = 8이다.

예를 들어, 아래와 같은 경우, 모든 모래시계가 0을 가리키는 순간이 존재한다.

 

 

[알고리즘]

1 ~ n의 숫자를 원형으로 배열하는 가짓수는 (n - 1)!이다. 

다만, 이 문제의 경우 동일한 배열이라도 시작위치가 다르면 서로 다른 케이스가 되기 때문에 전체 가짓수는 n!이 된다.

즉, [1, 2, 3, 4, 5, 6, 7, 8] ~ [8, 7, 6, 5, 4, 3, 2, 1] 모든 순열에 대해서 조건에 맞는 배열을 찾으면 된다.

(맨 처음에 위치한 숫자가 시작 위치)

 

위 예시에서 봤듯이 맨 처음 시작하는 모래시계가 n ( = 8)이라면, 무조건 2분 뒤에 모든 모래 시계가 0을 나타내게 된다.

8을 시작 위치로 가지는 배열의 가짓수는 총 7! = 5040개이다.

이제 나머지 경우에 대해서만 탐색하면 된다.

 

이 문제에서 가장 까다로운 부분은 무한히 진행해도 0, 0, 0, 0, ... 0이 나타나지 않는 경우에 대해서 어떻게 처리할지이다.

적당한 상한선을 설정할 필요가 있다. 상한선을 너무 크게 잡으면 탐색 시간이 오래 걸리고, 너무 낮게 잡으면 혹여나 나중에 0, 0, 0, 0, ... 0이 나타나는 케이스를 놓칠 수가 있다.

 

8개의 모래시계가 있다면 8분 마다 동일 과정이 반복된다. 단, 8분 후 원래 자기 자신으로 돌아온다는 보장은 없다.

예를 들어, 8번 모래 시계의 모래 양이 8분 후에 8이 아니고 0, 1, 2, 3, ... 7일 수도 있다.

8 -> 8, 즉 원래 자신으로 돌아온다면, 16분 후에도 8일 것이고 24분 후에도 8일 것이다.

8 -> 7 이라면, 1번 더 로테이션을 돌린다.

8 -> 7 -> 7이라면 그 이후에는 계속 7이 반복될 것이다.

8 -> 7 -> 6이라면 1번 더 로테이션을 돌린다.

8 -> 7 -> 6 -> 6이라면 그 이후에는 계속 6이 반복될 것이다.

8 -> 7 -> 6 -> 5라면 1번 더 로테이션을 돌린다.

... 이런 식으로 반복하면 결국에는 8번 로테이션 이전에는 무조건 반복되는 패턴이 등장하게 된다.

(물론 대부분의 경우에는 그보다 일찍 반복 패턴이 등장하겠지만.)

8보다 작은 숫자의 모래시계는 당연히 그 이전에 이미 반복되는 패턴이 등장한다. 

 

n = 8인 경우에는 위 처럼 상한선을 잡아도 충분히 빠르게 탐색이 가능하다.

 

아래는 코드

#include <stdio.h>
#include <stdbool.h>
#define N 8

int sandGlass[N] = { 0 };
bool isUsed[N] = { 0 };
int count = 0;

void solve(int index);
bool check(int* sandglass);;
void copyArr(int* arr1, int* arr2);
void printArr(int* arr);
int main() {
    int index = 0;
    int factorial = 1;
    solve(index);
    for (int i = 1; i < N; i++) {
        factorial *= i;
    }
    count += factorial;			// (N - 1)!를 더해준다.
    printf("count = %d\n", count);
}
void solve(int index) {
    if (index == N) {
        if (check(sandGlass) == true)
            count++;
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (isUsed[i - 1] == true)
            continue;
        if (index == 0 && i == N)	// N으로 시작하는 경우는 제외
            continue;
        sandGlass[index] = i, isUsed[i - 1] = true;
        solve(index + 1);
        sandGlass[index] = 0, isUsed[i - 1] = false;
    }
}
bool check(int* sandglass) {
    int cnt = 0;
    int pos = 0;
    int temp[N];
    copyArr(temp, sandglass);
    while (cnt < N * N) {
        // 각 모래시계 1씩 감소
        for (int i = 0; i < N; i++) {
            if (temp[i])
                temp[i]--;
        }
        // 모래시계 뒤집기
        for (int i = pos; i < pos + sandglass[pos]; i++) {
            int j = i % N;
            temp[j] = sandglass[j] - temp[j];
        }
        bool flag;
        for (int i = 0; i < N; i++) {
            flag = temp[i] == 1;
            if (!flag)
                break;
        }
        // flag가 true로 유지되면, 즉 모든 temp[i]가 1이면
        // 모든 모래시계의 모래 양이 1이면 1분 후 모두 0이 된다.
        if (flag) {		
            return true;
        }
        cnt++;
        pos = (pos + 1) % N;
    }
    return false;
}
void copyArr(int* arr1, int* arr2) {
    for (int i = 0; i < N; i++)
        arr1[i] = arr2[i];
}
void printArr(int* arr) {
    for (int i = 0; i < N; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

 

아래는 정답

 

참고로 책에서는 패턴을 저장하여, 동일 패턴이 나타나면 탐색을 멈추는 방법을 사용했다.

 

참고로, 최대 시간이 걸리는 배열 방법은 { 7, 8, 3, 5, 6, 2, 4, 1 }이고 43분만에 { 0, 0, 0, 0, 0, 0, 0, 0}이 된다.