c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q47 반전으로 만드는 엇갈리게 놓기

[문제]
앞이 검정, 뒤가 흰색인 2n 장의 카드가 원형으로 나열되어 있다. 처음 n 장은 검정색, 나중 n 장은 흰색이 보이도록 배치되어 있다. 여기서 연속하는 3장의 카드를 뒤집는 과정을 최소 횟수로 반복하여, 2n 장의 카드가 흑백이 번갈아 나타나도록 하고자 한다.
예를 들어, n = 4인 경우, 아래 2가지 방법이 가능하며, 최소 횟수는 4회이다.
1) 0 -> 5 -> 6 -> 7
2) 1 -> 2 -> 3 -> 4

n = 8, 즉 총 16장의 카드가 있을 때 최소 횟수는?
 
 
[알고리즘]
n, n+1, n+2의 카드를 뒤집는 것을 편의상 n번 카드를 선택했다 라고 표현하기로 한다.
1) 같은 카드를 2 번 선택하면 결국 원래 상태로 되돌아오므로 의미가 없다.
즉, 각 카드는 2번 이상 선택되지 않는다.
=> 최소 횟수는 2n번을 넘지 않는다. 
2) 카드를 선택하는 순서는 중요하지 않다. 즉, 1번 카드 선택 후 3번 카드를 선택하든, 3번 카드를 먼저 선택하고 1번 카드를 선택하든 결과는 동일하다.
=> 선택하는 카드 번호가 점점 커지는 경우에 대해서만 살펴보면 된다.
예를 들어, 0 -> 1 -> 2 -> 6 -> ... 등등
3) 색이 반전되기 위해서는 홀수 번 뒤집어져야 하고, 색이 그대로 유지되기 위해서는 짝수 번 뒤집어져야 한다.
즉, 아래 그림과 같이 각 카드가 뒤집어진 수를 확인하여 인접한 카드끼리 더했을 때 홀수가 되되, n - 1번 카드와 n번 카드를 더했을 때만 예외적으로 짝수가 되어야 한다.

 
이를 반영한 코드는 아래와 같다.

#include <stdio.h>
#include <stdbool.h>
#define N 8
void solve(int prev, int index);
void print_arr(int* arr);
bool check_sum(int* sum);
int arr[2 * N] = { 0 };
int sum[2 * N] = { 0 };		// 각각의 카드가 뒤집어진 횟수를 기록
int min_cnt = 2 * N;
int main() {
    int prev = -1, depth = 0;
    solve(prev, depth);
    printf("min_cnt = %d\n", min_cnt);
}
void solve(int prev, int depth) {
    if (depth > min_cnt)
        return;
    if (check_sum(sum) == true) {
        min_cnt = min_cnt > depth ? depth : min_cnt;
        if (depth == min_cnt) {
            printf("min_cnt = %d: ", min_cnt);
            print_arr(arr);
        }
        return;
    }
	
    for (int i = prev + 1; i < 2 * N; i++) {
        arr[depth] = i;
        for (int j = i; j < i + 3; j++)
            sum[j % (2 * N)]++;		// j가 2N 이상인 경우 0부터 다시 시작해야 함.

        solve(i, depth + 1);

        arr[depth] = 0;
        for (int j = i; j < i + 3; j++)
            sum[j % (2 * N)]--;
    }
}
// 인접한 값의 합이 홀수이되, sum[N - 1] + sum[N]은 짝수
bool check_sum(int* sum) {				
    for (int i = 0; i < 2 * N - 1; i++) {
        bool flag = (sum[i] + sum[i + 1]) % 2 == 1;
        if (i != N - 1 && !flag)
            return false;
        if (i == N - 1 && flag)
            return false;
    }
    return true;
}
void print_arr(int* arr) {
    for (int i = 0; i < 2 * N; i++) {
        if (i != 0 && arr[i] == 0)
            continue;
        printf("%d ", arr[i]);
    }
    printf("\n");
}

아래는 결과.
정답은 8회이며, 2가지 방법이 가능하다. 
정답을 잘 보면, 2가지 방법에서 서로 겹치는 숫자가 없는 것을 볼 수 있다.