[C/Python] 백준 1914번: C로 Big Integer 구현하기

📎 백준 1914번 풀러 가기

1914번: 하노이 탑

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

---

재귀함수를 배울 때 단골로 등장하는 하노이탑 문제이다.

예전에 C로 구현을 했었는데, 제출을 했었는데 자꾸 틀렸다고 나왔었다.

 

왜 그런가 했더니, 옮긴 횟수는 2^n-1인데, 원판의 개수가 100까지 가능하니,

1,267,650,600,228,229,401,496,703,205,375 를 저장해서 출력할 수 있어야 한다.

그러나 이 수는 너무너무 커서 long long의 범위를 넘어가버리는 것이었다.

그럼 이걸 구하기 위해서는 Big Integer를 C로 구현해야 한다는 것인데,

최근에 Java나 Python같은 언어들은 자체적으로 Big Integer를 지원하므로

요즘에 보는 코딩테스트에서는 주요하게 다루지 않는 부분이라고 들었다.

(그렇다더라- 라고만 들었다. 나는 아직 코딩테스트를 준비해본 적이 없다.)

 

그래서! 나도 이번에는 오랜만에 Python으로 풀었다.

파이썬을 한 지 거의 1년 만이라, print를 써야 하는데 printf를 쓰고, 매개변수에 자료형을 집어넣고 해서

구조를 짜는건 금방 했는데 문법에 맞게 고치는데 시간이 좀 걸린 것 같다.

 

➕[추가]

파이썬으로 풀고 제출을 하긴 했는데, 명색이 컴공생인데 Big Integer를 C로 구현을 안하고 넘어간다는건

말도 안 된다 기가 안 산다 컴공생이 그래도 되는거냐 같은 생각에 양심이 아주 콕콕콕 찔려서

1914번을 C로도 구현을 했다.

 

파이썬과 코드의 구조는 똑같지만, 파이썬에서는 쉽게 구현한 거듭제곱을

C에서 power라는 함수로 추가로 구현하였다.

 

작년에는 Big Integer 덧셈을 했었는데, 이번에는 거듭제곱이라니 뭔가 발전한 느낌이 들어서 기분이 좋다💕

 

그리고, 작년에 Big Integer를 구현할 때는 우리가 생각하는 숫자를 그대로 쓰기 위해

예를 들어 1234라는 숫자가 있으면 arr[0] = 1, arr[1] = 2, arr[2] = 3, arr[4] = 4 로 정해서

배열의 끝에서 앞으로 내려와야 했기 때문에 약간 복잡했었다.

 

이번에는! 약간의 생각의 전환을 해보자 해서

arr[0] = 4, arr[1] = 3, arr[2] = 2, arr[1] = 1의 역순으로 저장을 한 후,

for문을 거꾸로 돌려 출력을 했다.

기분탓인지는 모르겠지만 전자의 방법보다 훨씬 쉽게 느껴졌다!

---

아래는 내가 Python으로 구현한 코드👇

def hanoi(num, h_from, temp, to):
    if num == 1:
        print('%d %d' % (h_from, to))
    else:
        hanoi(num-1, h_from, to, temp)
        print('%d %d' % (h_from, to))
        hanoi(num-1, temp, h_from, to)


a = int(input())
times = 2**a - 1
print(times)
if a <= 20:
    hanoi(a, 1, 2, 3)

아래는 내가 C로 구현한 코드👇

#include <stdio.h>
#define MAX 35

void power(int x, int n, char arr[])
{
    int temp = 0;
    int last = 0;
    int cnt = 0;
    arr[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= last; j++)
        {
            temp = arr[j] * x + cnt;
            if (temp >= 10)
            {
                arr[j] = temp % 10;
                cnt = temp / 10;
                if (j == last)
                {
                    arr[++last] = cnt;
                    cnt = 0;
                    break;
                }
            }
            else
            {
                arr[j] = temp;
                cnt = 0;
            }
        }
    }
    arr[0] -= 1;
    for (int i = last; i >= 0; i--)
    {
        printf("%d", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int n = 0;
    char result[MAX] = {0};
    double tmp = 0;
    scanf("%d", &n);

    power(101, n, result);
}

---

✍새로 안 사실들

1. 파이썬은 거듭제곱을 연산자로 제공하고 있다. 👉 밑(base) ** 지수(exponent) 

2. (위에서는 적지 않았지만) WSL2는 XWindow를 통해 gui를 사용할 수 있다.