c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q49 완벽한 셔플

[문제] 1 ~ 2n 까지 숫자가 적힌 카드가 각 1장씩 일렬로 순서대로 배치되어 있다.

이 카드들을 다음과 같은 방법으로 섞는다고 한다.

앞쪽 n 장의 카드를 A그룹, 뒤쪽 n 장의 카드를 B그룹으로 나누어

A1B1A2B2....AnBn 순으로 배열한다.

아래 그림은 n = 5일 때 카드를 섞는 과정을 보여주며, 총 6번 섞을 때 맨 처음의 순서로 돌아오는 것을 보여준다.

 

n의 범위가 1 ~ 100이라고 할 때, 카드들이 맨 처음의 순서대로 돌아오기 위해서 몇 번 섞어야 하는지를 조사한다고 하자.

1) 2 * (n - 1)번 섞었을 때 원래의 자기 자신으로 돌아올 수 있는 n들의 값은? (최초이든 2번째, 3번째이든 상관없다)

2) 2 * (n - 1)번 섞었을 때 최초로 원래의 자기 자신으로 돌아오는 n들의 값은?

즉, 1)은 2)의 모든 가짓수를 포함한다.

위 예시에서 보여준 n = 5일 때는 섞는 횟수가 6회, 12회, 18회... 등일 때 자기 자신으로 돌아오므로 1), 2) 모두 해당사항이 없다.

 

[알고리즘]

카드의 순서를 배열에 저장한다고 할 때,

[0] ~ [2n - 1] 각 인덱스에 위치한 카드들이 셔플 후 어느 위치로 이동하는지 살펴본다.

1) index <= n - 1일 때는

[index]에 있는 카드들이 [index + index] 위치로 이동한다.

예를 들어, [1]에 있는 카드는 [2]로, [2]에 있던 카드는 [4]로, [3]에 있던 카드는 [6]으로 이동한다. [n - 1]에 있던 카드는 [2n - 2]로 이동한다.

2) n <= index <= 2n - 1일 때는

[index]에 있는 카드들이 [index - (2n - 1 - index)] = [2*index - 2n + 1] 위치로 이동한다.

즉, [n]에 있던 카드는 [1]로, [n + 1]에 있던 카드는 [3]으로, [2n - 2]에 있던 카드는 [2n - 3]으로 이동한다.

위 규칙을 토대로, 2번 카드의 위치 변화를 관찰한다.

예를 들어, n = 5일 때, 2번 카드의 제일 처음 위치는 [1]이다.

위 규칙에 따라 2번 카드는 다음과 같이 움직인다.

[1] -> [2] -> [4] -> [8] -> [7] -> [5] -> [1]

즉, 6번 만에 다시 원래 위치인 [1]로 되돌아 온다.

 

위 내용을 바탕으로 코드를 작성하면 다음과 같다.

1) 2 * (n - 1) 번 섞었을 때, 원래의 자기 자신으로 돌아오는 n 찾기

#include <stdio.h>
#include <stdbool.h>
int main() {
    int count = 0;
    for (int n = 1; n <= 100; n++) {
        int cnt = 0;
        int index = 1;
        bool revert;
        while (cnt < 2 * (n - 1)) {
            if (index <= n - 1) {
                index += index;
            }
            else {
                index -= (2 * n - 1 - index);
            }
            cnt++;
        }
        revert = index == 1;
        if (revert) {
            printf("n = %2d, cnt = %d\n", n, cnt);
            count++;
        }
    }
    printf("count = %d\n", count);
}

정답은 46개

 

2) 2*(n - 1)번 섞었을 때, 최초로 자기 자신으로 돌아오는 n 찾기

#include <stdio.h>
#include <stdbool.h>
int main() {
    int count = 0;
    for (int n = 1; n <= 100; n++) {
        int index = 1;
        int cnt = 0;
        bool revert;
        do {
            if (index <= n - 1) {
                index += index;
            }
            else {
                index -= (2 * n - 1 - index);
            }
            revert = index == 1;
            cnt++;
        } while (!revert);
        if (cnt == 2 * (n - 1)) {
            printf("n = %2d, cnt = %d\n", n, cnt);
            count++;
        }
    }
    printf("count = %d\n", count);
}

정답은 22개