c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q53 게으른 주판 (비트마스크 및 메모화 활용)

[문제]
주판을 가지고 1 ~ n까지 덧셈을 하려고 한다. 주판의 돌 움직을 최소로 하여 덧셈을 한다고 할 때,
n = 10일 때 최소 횟수는?
[주판에서 숫자 별 돌의 위치]

 
예를 들어, 8 + 9 덧셈을 한다고 할 때 돌의 움직임은 총 6번이다. (4 + 2)

그러나, 순서를 바꿔 9 + 8을 하면 돌의 움직임은 총 8번이다. (5 + 3)

즉, 덧셈 순서가 바뀌면 돌을 움직이는 횟수가 달라진다.
 
[알고리즘#1]
1) cntMat[10][10]을 준비하고, 숫자의 변화에 따른 돌의 움직임 횟수를 저장한다.
예를 들어, cntMat[0][4]는 0에서 4로 변할 때 돌의 움직임 횟수이며 4이다.
cntMat[4][8]은 4에서 8로 변할 때 돌의 움직임 횟수이며 2이다.
두 자릿수의 경우는 십의 자리와 일의 자리를 각각 구해서 더해준다. 예를 들어, 13에서 7을 더해 20이 된다고 했을 때
돌을 움직이는 횟수는 cntMat[1][2] + cntMat[3][0]이므로 1 + 3 = 4이다. 

cntMat 배열

 
2) 전체 탐색을 통해서 각 케이스의 cnt 값을 구하고, 그 중에서 최소 값을 구하면 된다.
1->2->3->...->10 부터 10->9->8->7...->1까지
아래는 코드. 지금까지 자주 활용했던 형태이다.

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#define N 12

int isUsed[N] = { false };
int cntMat[10][10] = { 0 };

void solve(int* min, int sum, int cnt, int depth);
void fillMatrix(int mat[][10]);
void printMatrix(int mat[][10]);
int main() {

    // 매트릭스 채우기
    fillMatrix(cntMat);

    int sum = 0;
    int cnt = 0;
    int depth = 0;
    int minCnt = -1;
    solve(&minCnt, sum, cnt, depth);
    printf("minCnt = %d\n", minCnt);
}
void solve(int* min, int sum, int cnt, int depth) {
    // cnt가 min보다 크면 리턴
    if (*min != -1 && cnt >= *min)
        return;

    // 숫자 10개를 모두 사용하면 cnt가 최소 횟수인지 확인한다.
    if (depth == N) {
        if (*min == -1)
            *min = cnt;
        else
            *min = *min > cnt ? cnt : *min;
        return;
    }

    // 재귀를 통해서 전체 탐색한다.
    for (int i = 1; i <= N; i++) {
        if (isUsed[i - 1])
            continue;
        int temp1 = sum, temp2 = sum + i;
        int count = cnt;
        while (temp2 > 0) {
            count += cntMat[temp1 % 10][temp2 % 10];
            temp1 /= 10, temp2 /= 10;
        }
        isUsed[i - 1] = true;
        solve(min, sum + i, count, depth + 1);
        isUsed[i - 1] = false;
    }
}
void fillMatrix(int mat[][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1; j < 10; j++) {
            int* p = &mat[i][j];
            int dif = (int)abs(i - j);
            if (dif >= 5) {
                *p = dif - 4;
            }
            else {
                if (i <= 4 && j >= 5) {
                    *p = 6 - dif;
                }
                else if (i >= 5 && j <= 4) {
                    *p = 6 - dif;
                }
                else
                    *p = dif;
            }
            mat[j][i] = *p;
        }
    }
}

정답은 26회이다.

단, n = 10일 때는 금방 구해지지만 11만 되어도 시간이 많이 걸리고 15일 때는 수 분 이상 소요된다.
따라서, 이전 문제에서도 활용했던 비트마스크와 메모화 기법을 활용해본다.
 
[알고리즘#2]
1) cntMat을 구하는 것은 동일하다.

2) state 변수를 정의하여, 1 ~ 10 중 어느 숫자가 사용되었는지를 저장한다.
예를 들어, 1, 5, 6, 9, 10이 사용되었다고 하자. 그러면
state = 11001 10001 (이진법) = 817 (십진법)이 된다.
1 ~ 10까지 모두 사용되었다면
state = 11111 11111 (이진법) = 1023 (십진법)이 된다.

3) minCnt(state) 함수를 정의한다. 이 함수는 어떤 state 상태에서 남은 숫자들을 활용하여 최소 횟수로 덧셈을 할 때, 그 횟수를 리턴하는 함수이다.
예를 들어, 1, 5, 6, 9, 10이 사용되어 state = 11001 10001(2진법) = 817(10진법)이라고 하자.
그러면 지금까지의 sum 값은 1 + 5 + 6 + 9 + 10 이므로 31이고, 남은 수는 당연히 2, 3, 4, 7, 8이다.
이제 sum = 31인 상태에서 2, 3, 4, 7, 8 을 최소 횟수로 더한다고 할 때, 그 최소 횟수가 바로 minCnt(11001 10001)이다.
(편의상 2진법으로 표현하기로 한다.)
(sum = 31이 될때까지 돌이 움직인 횟수는 신경쓰지 않는다. 그저, 남은 숫자를 가지고 최소 횟수로 더하는 것만 고려한다.)

4) minCnt(11001 10001)은 다음과 같이 구한다.

minCnt(11001 10001)은 다음 5가지 값들 중 최소값이다.

i) 2를 더하는 케이스: minCnt(11001 10011) + getCnt(31, 33)

ii) 3을 더하는 케이스: minCnt(11001 10101) + getCnt(31, 34)

iii) 4를 더하는 케이스: minCnt(11001 11001) + getCnt(31, 35)

iv) 7을 더하는 케이스: minCnt(11011 10001) + getCnt(31, 38)

v) 8을 더하는 케이스: minCnt(11110 10001) + getCnt(31, 39)

getCnt(val1, val2)는 val1 -> val2로 바꿀 때 돌을 움직이는 횟수이다.

예를 들어, getCnt(31, 33)은 31에서 33으로 돌을 바꾸는 횟수이며, 값은 2이다.

getCnt(31, 39)는 31에서 39로 돌을 바꾸는 횟수이며 값은 4이다.

4) 결국 우리가 구하고자 하는 것은 minCnt(00000 00000)이다.

위에서 살펴본 것과 동일하게 minCnt(00000 00000)은 다음 10가지 경우 중 최소 값이다.

i) minCnt(00000 00001) + getCnt(0, 1) 

ii) minCnt(00000 00010) + getCnt(0, 2) 

iii) minCnt(00000 00100) + getCnt(0, 3) 

...

ix) minCnt(01000 00000) + getCnt(0, 9) 

x) minCnt(10000 00000) + getCnt(0, 10)  
 

minCnt(00000 00001)은 다시 아래 9가지 경우 중 최소 값이다.

i) minCnt(00000 00011) + getCnt(1, 3)  

ii) minCnt(00000 00101) + getCnt(1, 4)  

iii) minCnt(00000 01001) + getCnt(1, 5)  

...

iix) minCnt(01000 00001) + getCnt(1, 10)

ix) minCnt(10000 00001) + getCnt(1, 11)
 
이런 식으로 반복해 나가는 것이다.
minCnt 함수를 코드로 나타내면 다음과 같다.

int minCnt(unsigned long state) {
    // 숫자를 모두 사용하면
    if (state == (1 << N) - 1)
        return 0;
    // 메모에 값이 기록되어 있으면 활용한다.
    if (memo[state])
        return memo[state];

    int minValue = -1;
    int sum = getSum(state);	// state로부터 지금까지의 합계 값을 구한다.
    for (int i = 1; i <= N; i++) {
        unsigned long mask = 1 << (i - 1);
        
        if (state & mask) {		// 이미 사용된 숫자이면 스킵한다.
            continue;
        }
        int newValue = minCnt(state | mask) + getCnt(sum, sum + i);
        if (minValue == -1) {
            minValue = newValue;
        }
        else {
            minValue = minValue > newValue ? newValue : minValue;
        }
    }
    memo[state] = minValue;
    return minValue;
}

 
5) 메모화

위 비트마스크를 사용한 것은 결국은 메모화를 하기 위한 목적이었다.

메모화를 사용하면 중복된 state에 대해서 탐색 횟수를 크게 줄일 수 있다.

예를 들어, 5 + 6이나 6 + 5나 state는 00001 10000로 동일하며, minCnt(00001 10000) 값 역시 동일하다.

따라서 memo[00001 10000]에 minCnt(00001 10000)을 기록해두었다면 두 번째 등장할 때부터는 그 값을 활용하면 된다.
 
아래는 전체 코드

#include <stdio.h>
#include <stdlib.h>
#define N 10

int* memo = NULL;
int cntMat[10][10] = { 0 };

void fillMatrix(int mat[][10]);
int minCnt(unsigned long state);
int getSum(unsigned long state);
int getCnt(int sum1, int sum2);
int main() {
    // 메모 초기화
    unsigned long sz = 1 << N;
    memo = (int*)malloc(sizeof(int) * sz);
    for (unsigned long i = 0; i < sz; i++)
        memo[i] = 0;

    // cntMat 채우기
    fillMatrix(cntMat);

    // 최소 횟수 구하기
    unsigned long state = 0;
    printf("minCnt = %d\n", minCnt(state));

    free(memo);
}
void fillMatrix(int mat[][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1; j < 10; j++) {
            int* p = &mat[i][j];
            int dif = (int)abs(i - j);
            if (dif >= 5) {
                *p = dif - 4;
            }
            else {
                if (i <= 4 && j >= 5) {
                    *p = 6 - dif;
                }
                else if (i >= 5 && j <= 4) {
                    *p = 6 - dif;
                }
                else
                    *p = dif;
            }
            mat[j][i] = *p;
        }
    }
}
int minCnt(unsigned long state) {
    // 숫자를 모두 사용하면
    if (state == (1 << N) - 1)
        return 0;
    // 메모에 값이 기록되어 있으면 활용한다.
    if (memo[state])
        return memo[state];

    int minValue = -1;
    int sum = getSum(state);	// state로부터 지금까지의 합계 값을 구한다.
    for (int i = 1; i <= N; i++) {
        unsigned long mask = 1 << (i - 1);
        
        if (state & mask) {		// 이미 사용된 숫자이면 스킵한다.
            continue;
        }
        int newValue = minCnt(state | mask) + getCnt(sum, sum + i);
        if (minValue == -1) {
            minValue = newValue;
        }
        else {
            minValue = minValue > newValue ? newValue : minValue;
        }
    }
    memo[state] = minValue;
    return minValue;
}
int getSum(unsigned long state) {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        int mask = 1 << (i - 1);
        if (state & mask)
            sum += i;
    }
    return sum;
}
// sum1에서 sum2로 갈 때 움직이는 돌의 횟수
int getCnt(int sum1, int sum2) {
    int cnt = 0;
    while (sum2 > 0) {
        cnt += cntMat[sum1 % 10][sum2 % 10];
        sum1 /= 10, sum2 /= 10;
    }
    return cnt;
}

 
이렇게 하면 n = 15 뿐만 아니라 심지어 n = 20일 때 조차도 순식간에 값을 구할 수 있다.

n = 20일 때의 정답 (약 1초 정도 걸렸다.)