신기한 방법으로 풀었던 문제

일반적이지 않은 신기한 방법으로 풀었던 문제들을 어떻게 풀었는지 기록해보았다.

Dance Dance Revolution

2005년, 다이나믹 프로그래밍을 몰랐다. 다이나믹 프로그래밍이 뭔지는 알았지만, 스스로 점화식을 만들지 못했다. 점화식을 누가 적어주면 구현은 할 수 있는 그런 상태였다.

스스로 문제를 풀어보기 위해 일단 모든 방법을 다 만들어보기로 했다.

눌러야 하는 발판: 1 → 2 → 1 → 4

가장 처음: (0, 0)

첫 번째 발판 (1)

  • (0, 0) → (1, 0): 2
  • (0, 0) → (0, 1): 2

두 번째 발판 (2)

  • (0, 0) → (1, 0) → (2, 0): 5
  • (0, 0) → (1, 0) → (1, 2): 4
  • (0, 0) → (0, 1) → (2, 1): 4
  • (0, 0) → (0, 1) → (0, 2): 5

세 번째 발판 (1)

  • (0, 0) → (1, 0) → (2, 0) → (1, 0): 8
  • (0, 0) → (1, 0) → (2, 0) → (2, 1): 7
  • (0, 0) → (1, 0) → (1, 2) → (1, 2): 5
  • (0, 0) → (1, 0) → (1, 2) → (1, 1): 7
  • (0, 0) → (0, 1) → (2, 1) → (1, 1): 7
  • (0, 0) → (0, 1) → (2, 1) → (2, 1): 5
  • (0, 0) → (0, 1) → (0, 2) → (1, 2): 7
  • (0, 0) → (0, 1) → (0, 2) → (0, 1): 8

네 번째 발판 (4)

  • (0, 0) → (1, 0) → (2, 0) → (1, 0) → (4, 0): 11
  • (0, 0) → (1, 0) → (2, 0) → (1, 0) → (1, 4): 10
  • (0, 0) → (1, 0) → (2, 0) → (2, 1) → (4, 1): 11
  • (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 4): 10
  • (0, 0) → (1, 0) → (1, 2) → (1, 2) → (4, 2): 8
  • (0, 0) → (1, 0) → (1, 2) → (1, 2) → (1, 4): 9
  • (0, 0) → (1, 0) → (1, 2) → (1, 1) → (4, 1): 10
  • (0, 0) → (1, 0) → (1, 2) → (1, 1) → (1, 4): 10
  • (0, 0) → (0, 1) → (2, 1) → (1, 1) → (4, 1): 10
  • (0, 0) → (0, 1) → (2, 1) → (1, 1) → (1, 4): 10
  • (0, 0) → (0, 1) → (2, 1) → (2, 1) → (4, 1): 9
  • (0, 0) → (0, 1) → (2, 1) → (2, 1) → (2, 4): 8
  • (0, 0) → (0, 1) → (0, 2) → (1, 2) → (4, 2): 10
  • (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 4): 11
  • (0, 0) → (0, 1) → (0, 2) → (0, 1) → (4, 1): 10
  • (0, 0) → (0, 1) → (0, 2) → (0, 1) → (0, 4): 11

이렇게 다 써놓고 보다보니 몇 가지 규칙을 발견하게 되었다. 세 번째 발판의 경우를 보면 세 번째 발판을 누른 (왼발, 오른발)의 위치가 같은데 사용한 힘이 다른 경우가 있었다. 문제에서는 최소의 힘을 구하라고 했는데, 최솟값이 아닌 값을 유지할 필요가 없다.

세 번째 발판에서 네 번째 발판으로 넘어가는 모든 방법을 번갈아가면서 쳐다보다보니 점화식을 만들 수 있게 되었다.

D[n][l][r] = N번째 발판을 밟았고, 왼발은 l, 오른발은 r에 있을 때 최소의 힘

장애물 설계

위의 2342번 문제로 다이나믹 프로그래밍을 이해할 수 있게 된지 한 달 정도 지난 후에 풀었던 문제이다. 문제의 입력 값이 m과 k로 두 개였기 때문에, 아마 2차원 다이나믹으로 해결 할 수 있을 것이라 생각했다. 아직 이 문제의 점화식을 만들어 낼 능력은 없다고 생각했기 때문에, 모든 방법을 다 찍어보기로 했다.

  • D[m][k] = m개의 장애물로 만들 수 있는 난이도 k인 경기장의 개수

보통 D[i][j]의 형태로 점화식이 나오는 경우 D[i][j]는 D[i-1][j], D[i-1][j-1], D[i][j-1]의 값의 조합으로 구할 수 있는 경우가 가장 많았다.

또 다시 백트래킹을 이용해서 (M, K)의 값이 (4, 3), (3, 3), (4, 2), (3, 2)의 값을 모두 구해보기로 했다. (4, 3)을 구할 때는 (3, 2), (3, 3)의 값만 필요했기 때문에, 이 글에서 (4, 2)는 적지 않았다.

M = 3, K = 2인 경우

1 1 3 3 2 21 3 3 2 2 12 2 1 1 3 32 2 1 3 3 12 2 3 3 1 1
2 3 3 2 1 13 3 1 1 2 23 3 1 2 2 1

M = 3, K = 3인 경우

1 1 2 2 3 31 1 2 3 3 21 2 2 1 3 31 2 2 3 3 11 2 3 3 2 1
1 3 3 1 2 2

M = 4, K = 3인 경우

1 1 2 2 4 4 3 31 1 2 4 4 3 3 21 1 3 3 2 2 4 41 1 3 3 2 4 4 21 1 3 3 4 4 2 2
1 1 3 4 4 3 2 21 1 4 4 2 2 3 31 1 4 4 2 3 3 21 2 2 1 4 4 3 31 2 2 4 4 3 3 1
1 2 4 4 3 3 2 11 3 3 1 4 4 2 21 3 3 2 2 1 4 41 3 3 2 2 4 4 11 3 3 2 4 4 2 1
1 3 3 4 4 2 2 11 3 4 4 3 2 2 11 4 4 1 3 3 2 21 4 4 2 2 1 3 31 4 4 2 2 3 3 1
1 4 4 2 3 3 2 11 4 4 3 3 1 2 22 2 1 1 3 3 4 42 2 1 1 3 4 4 32 2 1 3 3 1 4 4
2 2 1 3 3 4 4 12 2 1 3 4 4 3 12 2 1 4 4 1 3 32 2 3 3 1 1 4 42 2 3 3 1 4 4 1
2 2 3 3 4 4 1 12 2 3 4 4 3 1 12 2 4 4 1 1 3 32 2 4 4 1 3 3 12 3 3 2 1 1 4 4
2 3 3 2 1 4 4 12 3 3 2 4 4 1 12 3 3 4 4 2 1 12 3 4 4 3 2 1 12 4 4 2 1 1 3 3
2 4 4 2 1 3 3 12 4 4 2 3 3 1 13 3 1 1 2 2 4 43 3 1 1 2 4 4 23 3 1 2 2 1 4 4
3 3 1 2 2 4 4 13 3 1 2 4 4 2 13 3 1 4 4 1 2 23 3 4 4 1 1 2 23 3 4 4 1 2 2 1
3 4 4 3 1 1 2 23 4 4 3 1 2 2 14 4 1 1 2 2 3 34 4 1 1 2 3 3 24 4 1 2 2 1 3 3
4 4 1 2 2 3 3 14 4 1 2 3 3 2 14 4 1 3 3 1 2 2

M = 3, K = 3인 경우는 M = 4, K = 3인 경우에서 3번씩 등장했다. 여기서 3은 K와 같다.

M = 3, K = 2인 경우는 M = 4, K = 3인 경우에서 5번씩 등장했다. 여기서 5는 2M-K와 같다.

둘을 종합해 D[M][K] = D[M-1][K]×K + D[M-1][K-1]×(2M-K)를 유도할 수 있었다.

마법 구슬

문제 링크: BOJ 2301번

KOI 2006년 고등부 3번 문제이다. 당시에 문제를 보고 바로 느낀 생각은 이 문제는 내가 풀 수 있는 문제의 난이도가 아니라는 생각이었다. 그런데, 문제를 보니 가능한 입력의 조합이 그렇게 크지 않다고 느꼈다.

입력으로 두 정수 N과 M이 주어지는데, 21 ≤ N ≤ 213, 1 ≤ M ≤ N 을 만족하고, N은 항상 2의 거듭제곱꼴이었다. 즉, 가능한 입력의 조합이 214 = 16384개이다.

시험 시간 동안 최대한 많은 입력에 대한 정답을 구하기로 했다. 정답을 구하고, 정답을 어디간에 적어두고, 이를 코드에 옮기기로 결정했다. 요약하면 코드를 작성하는 코드를 만들기로 했다.

코드를 만들면 다음과 같다. 실행 시간이 매우 오래 걸리지만, 시험 시간은 3-4시간 정도 되었기 때문에, 꽤 많은 경우의 답을 구할 수 있었다. 실제로 사용한 코드는 저 코드에서 실행 시간이 지나치게 길 경우 스킵하는 부분을 추가했다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
bool check[10000];
int a[10000];
int n;
bool go(int index, int cnt) {
    if (cnt == 0) return true;
    for (int i=1; i<=n; i++) {
        if (a[i] != 0) {
            continue;
        }
        int diff = i-index;
        if (diff < 0) diff = -diff;
        if (check[diff]) continue;
        check[diff] = true;
        a[i] = cnt;
        if (go(i, cnt-1)) return true;
        a[i] = 0;
        check[diff] = false;
    }
    return false;
}
int main() {
    for (int i=2; i<=16; i*=2) {
        for (int j=1; j<=i; j++) {
            memset(check,false,sizeof(check));
            memset(a,0,sizeof(a));
            n = i;
            a[j] = i;
            go(j, i-1);
            printf("if (n == %d && m == %d) ", i, j);
            printf("printf(\"");
            for (int k=1; k<=i; k++) {
                printf("%d", a[k]);
                if (k != i) printf(" ");
            }
            printf("\");\n");
        }
    }
    return 0;
}

위와 같은 코드를 이용하면 다음과 같은 출력을 구할 수 있고, 이제 출력된 내용을 다른 소스에 붙여 넣어서 문제를 푸는 소스 코드를 완성할 수 있다.

if (n == 2 && m == 1) printf("2 1");
if (n == 2 && m == 2) printf("1 2");
if (n == 4 && m == 1) printf("4 2 1 3");
if (n == 4 && m == 2) printf("2 4 3 1");
if (n == 4 && m == 3) printf("1 3 4 2");
if (n == 4 && m == 4) printf("3 1 2 4");
if (n == 8 && m == 1) printf("8 6 4 2 1 3 5 7");
if (n == 8 && m == 2) printf("4 8 6 1 2 7 3 5");
if (n == 8 && m == 3) printf("3 5 8 7 1 6 4 2");
if (n == 8 && m == 4) printf("7 5 3 8 2 1 4 6");
if (n == 8 && m == 5) printf("2 7 4 5 8 6 1 3");
if (n == 8 && m == 6) printf("7 5 2 1 4 8 3 6");
if (n == 8 && m == 7) printf("7 2 5 4 1 3 8 6");
if (n == 8 && m == 8) printf("7 5 3 1 2 4 6 8");
if (n == 16 && m == 1) printf("16 14 12 10 8 6 4 2 1 3 5 7 9 11 13 15");
if (n == 16 && m == 2) printf("12 16 14 6 10 8 2 4 3 1 9 5 7 15 11 13");
if (n == 16 && m == 3) printf("8 10 16 12 14 6 3 5 1 2 15 4 7 13 11 9");
if (n == 16 && m == 4) printf("12 10 8 16 6 4 2 15 14 1 13 3 5 7 9 11");
if (n == 16 && m == 5) printf("11 9 3 7 16 5 15 13 1 2 14 4 12 6 8 10");
if (n == 16 && m == 6) printf("10 8 2 6 4 16 15 12 14 1 3 13 11 5 7 9");
if (n == 16 && m == 7) printf("15 13 11 9 7 2 16 5 3 4 1 6 8 10 12 14");
if (n == 16 && m == 8) printf("15 13 11 9 7 4 6 16 2 1 5 3 8 10 12 14");
if (n == 16 && m == 9) printf("15 13 11 9 1 7 4 6 16 3 2 5 8 10 12 14");
if (n == 16 && m == 10) printf("15 13 11 9 4 8 6 1 2 16 7 3 5 10 12 14");
if (n == 16 && m == 11) printf("15 13 11 2 9 8 6 4 1 5 16 3 7 10 12 14");
if (n == 16 && m == 12) printf("15 13 11 2 4 6 10 8 9 1 7 16 5 3 12 14");
if (n == 16 && m == 13) printf("15 13 6 11 9 4 8 2 1 7 5 3 16 10 12 14");
if (n == 16 && m == 14) printf("15 13 9 11 7 2 4 6 5 1 12 3 8 16 10 14");
if (n == 16 && m == 15) printf("15 9 13 11 3 7 1 5 6 4 2 12 8 10 16 14");
if (n == 16 && m == 16) printf("15 13 11 9 7 5 3 1 2 4 6 8 10 12 14 16");

KOI는 ICPC처럼 문제에 대한 결과가 Yes/No만 있는 것이 아니기 때문에 위의 방법으로 부분 점수를 최대한 많이 획득할 수 있었다.

기하학문양

2013년 대전 ACM-ICPC C번 문제이다. 당시 우리팀은 A, F, G, I, J, K, L을 푼 상태였다. 다음으로 풀 문제를 찾던 중 매우 다이나믹 프로그래밍처럼 보이는 문제가 있었다.

문제를 요약하면 정수 n (3 ≤ n ≤ 50,000)이 주어졌을 때, 2 × n 직사각형 그리드와 2 × n 원형 그리드에서 만들 수 있는 스패닝 트리의 개수를 구하는 문제이다.

문제의 예제는 n = 3, n = 4, n = 10인 경우가 입력으로 주어지고 있었다. 문제에 변수가 하나밖에 없기 때문에, 아마도 d[n] 형태의 점화식이 나올 것으로 예상되었다.

n = 5, 6, 7, 8, 9에 대한 답을 구하면 값을 이용해서 점화식을 유추할 수 있을 것이라고 예상되었고, 백트래킹을 이용해서 답을 구하기로 했다.

정확하게 기억은 나지 않지만, N = 8까지 답을 구했었던 것 같고 다음과 같이 R[n]을 구할 수 있었다.

nR[n]
315
456
5209
6780
72911
810864

R[n]은 의외로 금방 구할 수 있었다.

R[3]과 R[4]를 보니 약 4배의 차이가 있었다. 4×R[3] = 60이고, R[4] = 56 와는 4의 차이가 났다. R[4]와 R[5]도 대략 4배의 차이가 있었는데, 계산해보니 4×R[4] = 224, R[5] = 209였다.

가장 처음에 4×R[3]과 R[4]가 4차이가 나는 것을 보고 R[n] = n×R[n-1] – n의 점화식이 나올 것으로 예상했는데, 4×R[4]와 R[5]의 차이가 15였기 때문에, 위의 예상이 빗나갔다. 그런데, 15는 R[3]에도 등장한다. 이제 R[5]와 R[6]도 한 번 구해보기로 했다.

4×R[5] = 836, R[6] = 780이고, 둘의 차이는 56이었다. 56은 R[4]로도 등장한다.

이를 이용해 R[n] = n×R[n-1] – R[n-2]를 유추할 수 있었다. 이 식을 이용하니 다른 값도 모두 일치했다.

이제 C[n]을 구해야 한다.

nC[n]
375
4384
51805
68100
735287
8150528

C[n]에 대해서도 위와 같은 과정을 거쳤으나 모두 실패했고, C[n]은 R[n]을 이용해서 구해보기로 했다.

nR[n]C[n]
31575
456384
52091805
67808100
7291135287
810864150528

위의 표를 종이에 써놓고 꽤 오랜 시간 살펴보았고, n×R[n]을 구해보았다.

nR[n]C[n]n×R[n]
3157545
456384224
520918051045
678081004680
729113528720377
81086415052886912

다시 살펴보다보니 C[5] = 1805인데, 5×R[5] = 1045, 4×R[4] = 224에서 5×R[5]에 2를 곱하고 거기서 4×R[4]를 빼면 C[5]가 나올 것 같았다.

구해보니 1045×2 – 224 = 1866 이었다. 1866에서 1805를 구하기 위해서 1866-1805 = 61 이 나왔고, 표에서 61을 만들어보려고 노력하니 5 + R[4] = 56 + 5 = 61이 나왔다.

이를 이용해 C[5]를 구해보면 C[5] = 5×R[5]×2 – 4×R[4] – (5 + R[4]) = 1805 가 나왔다.

식을 풀어보니 C[5] = 5×R[5]×2 – 4×R[4] – 5 – R[4] = 5×R[5]×2 – 5×R[4] – 5 이고, 일반화해보니 C[n] = n×R[n]×2 – n×R[n-1] – n 이다. n = 6을 계산해보았다.

C[6] = 6×R[6]×2 – 6×R[5] – 6 = 9360 – 1254 – 6 = 8100 이 나왔고, 실제로 C[6]의 값과 일치했다.

이런식으로 R[n]과 C[n] 식을 계산할 수 있었다.

  • R[n] = 4×R[n-1] – R[n-2]
  • C[n] = n×(2×R[n] – R[n-1] – 1)

이렇게 푸는데 1시간-1시간 반정도 걸렸던 것 같다.

Jukebox

매우 간단한 문제이다. mp3 파일이 입력으로 주어지고, 계이름을 적으면 되는 문제이다. 그냥 듣고 적어서 제출했다.

Luxor Catch-ya!

상형문자로 적혀있는 그림 파일이 입력으로 주어지고, 이를 알파벳으로 다시 적어서 내는 문제이다.

Easy, Hard 각각 800개씩 파일이 있고, 한 파일에 5개씩 상형문자가 있었다. 상형문자를 눈으로 보면서 한 글자씩 해석해서 풀었다. Easy를 풀다보니 상형문자를 대강 외워서 오히려 Hard를 더 빨리 풀었다.