이 문제는 60번에 이어서 연속으로 난이도 20% 문제이지만, 제 경우에는 그렇게 어렵지 않게 풀었던 문제입니다.


n각수 문제를 풀기 위해서는 n각수인 조건을 잘 검사하면 큰 무리가 없을 것이라 생각합니다.



이 문제는 두자릿수씩 겹치면서 순환하는 6개의 수가, 각각 3각수, 4각수, ..., 8각수가 되는 수열을 구하라는 것입니다.


3각수가 되는 4자리 수를 구한후, 뒤의 두자리수로 시작하는 4각수가 되는 수를 구하는 식으로 연결지어서 최종적으로 3각수의 첫두자리수로 끝나는 8각수를 만들면 됩니다.


제 경우에는 미리 n각수를 다 구한다음에, 해당수들이 순환하는지 검사하는 코드를 작성했습니다.  실제로 4자리 n각수가 많지는 않습니다.  모든 n각수는 2차식이기 때문에 상당히 빠르게 숫자가 커집니다.



#include <stdio.h>
#include <math.h>

int cyclic(int bitflag, int start, int end, int sum);
int polygonal[6][1000];
int pcount[6] = { 0, 0, 0, 0, 0, 0 };

int main()
{
    int pdiff[6] = { 1, 1, 1, 1, 1, 1 };
    int pdiff2[6] = { 1, 2, 3, 4, 5, 6 };

    for( int i = 0 ; i < 6 ; i++ )
    {
        int s = 0;
        for( int n = 0 ; ; n++, pdiff[i] += pdiff2[i] )
        {
            s += pdiff[i];
            if( s < 1000 ) continue;
            if( s >= 10000 ) break;
            if( s%100 < 10 ) continue;
            polygonal[i][pcount[i]++] = s;
        }
        printf("%d : %d\n", i, pcount[i]);
    }
    for( int i = 0 ; i < pcount[0] ; i++ )
    {
        int c = polygonal[0][i];
        int ans = cyclic(1, c%100, c/100, c);
        if( ans ) printf("Ans = %d\n", ans);
    }
}

int cyclic(int bitflag, int start, int end, int sum)
{
    if( bitflag == 0x3f )
    {
        if( start == end ) return sum;
        return 0;
    }
    for( int i = 1 ; i < 6 ; i++ )
    {
        if( (bitflag>>i)&1 ) continue;
        for( int j = 0 ; j < pcount[i] ; j++ )
        {
            int c = polygonal[i][j];
            if( c/100 == start )
            {
                int ans = cyclic(bitflag|(1<<i), c%100, end, sum+c);
                if( ans ) return ans;
            }
        }
    }
    return 0;
}


저작자 표시 비영리 변경 금지
신고



이번 문제는 처음으로 난이도 20%짜리 문제입니다.



소수쌍이라고 해서 특별한 수학적인 내용이 들어가 있는 것은 아닙니다.

3, 7 이 두개의 소수가 있다고 하면, 이 두개의 소수를 단순하게 이어서 37, 73을 만들었을 때, 이 수들도 소수가 되면, (3, 7)은 소수쌍이 되는 것입니다.


이러한 소수들은 무한히 존재하겠지만, 빈도가 많지는 않습니다.


이 문제를 풀기 위해서는 메모리를 사용해서 해당되는 셋들을 만들것인가가 중요했습니다.  그렇게 하려면, 너무 자료구조가 복잡해서, 약간의 꼼수를 사용했습니다.


일단, 소수들을 결합하기 위한 재료는 미리 저장을 해놓고, 소수들을 결합한 결과에 대한 소수 검사는 별도의 라이브러리를 이용했습니다.  그리고 min이라는 정적 변수를 두어서, 이 값을 이용해서 현재 구해진 최소값보다 예상값이 크면 더 이상 진행하지 않도록 했습니다.


이렇게 해도 시간이 꽤 걸리네요.  다시 좋은 알고리즘으로 짜고 싶기는 했지만, 일단 이 선에서 마무리를 했습니다.


아래는 소스입니다.



#include <stdio.h>
#include <time.h>
#include "isprime.h"

#define N   5
#define LIMIT   5000

int getminsum(int primes[], int pcount, int pset[][2], int n, int s, int sum)
{
    static int min = 0x7fffffff;

    if( n >= N ) return sum;
    for( int i = s ; i < pcount ; i++ )
    {
        if( sum+primes[i]*(N-n) >= min ) break;
        int c = 10;
        while( primes[i] >= c ) c *= 10;
        bool find = true;
        for( int j = 0 ; j < n ; j++ )
        {
            int t;
            t = pset[j][0]*c+primes[i];
            if( !isPrime(t) ) { find = false; break; }
            t = primes[i]*pset[j][1]+pset[j][0];
            if( !isPrime(t) ) { find = false; break; }
        }
        if( find == false ) continue;
        pset[n][0] = primes[i];
        pset[n][1] = c;
        int t = getminsum(primes, pcount, pset, n+1, i+1, sum+primes[i]);
        if( t < min ) min = t;
    }
    return min;
}

void solve1()
{
    static int primes[LIMIT];
    int pcount = 0;

    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;
    for( int p = 11 ; pcount < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 0 ; primes[i]*primes[i] <= p ; i++ )
        {
            if( (p%primes[i]) == 0 ) { isPrime = false; break; }
        }
        if( isPrime ) primes[pcount++] = p;
    }

    int pset[5][2];
    int minsum = getminsum(primes, LIMIT, pset, 0, 0, 0);

    printf("Ans = %d\n", minsum);
}


저작자 표시 비영리 변경 금지
신고



이번 문제는 난이도가 5%이기는 하지만, 실제로 정석대로 푼다면 5%보다 높을 것 같네요.


암호를 푸는 방법은 무식한 방법으로 반복대치를 하는 경우가 많습니다.  단순 반복대치를 하면 풀 수는 있겠지만, 보통 수만대의 컴퓨터를 동원해도 몇천년, 몇만년 이상 걸리는 경우가 허다합니다.  양자컴퓨터가 나온다면 좀 달라질 수 있겠지만요.



이 문제에서는 주어진 텍스트에 3글자 소문자로 이루어진 키를 가지고 암호를 푸는 것입니다.  원래 문제 의도(난이도 5%)였다면, 3글자 소문자 키를 생성하고, 그것에 의해서 영어의 일반 언어가 도출되는지를 검사하면 되겠죠.  예를 들어서 a, this, is, are, you, 등등이 될겁니다.


전 고전적인 방법, 즉, 암호키를 알기 힘들다는 가정하에서 풀어보았습니다.  물론 암호키의 길이는 알고 있어야 합니다.  일반적으로 단순 반복 XOR 암호화 방법은 이 방식으로 대부분의 일반 문서는 풀 수가 있습니다.  암호화 키에 비해서 문서가 너무 짧다면 어렵겠지만요.  통계학적인 방법을 이용해서 문제를 풀었습니다.


첫번째, 영어 단어에 많이 포함되는 문자들을 나였했습니다,  i, a, e, o, c, d, g, h, f 가 해당 됩니다.  그리고 공백문자를 까먹어서도 안 되겠죠.


그런 후에 암호화 키 길이에 맞게 반복되는 문자들의 도수 분포를 만듭니다.  그리고 도수 분포에 따라서 위에 자주 나오는 글자들을 대입해보는 것이죠.  그렇게 하면 암호키를 찾아낼 수 있습니다.


실제 실행한 화면은 다음과 같습니다.


12 6 48 8 5 5 18 0 18 28 6 12 2 0 18 25 7 4 5 28 17 15 0 3 0 0 0 0 0 0

3 2 4 1 0 0 0 1 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 70 0 11 0 5 0 0 1 1 0 0 0 1 1 0 2 1 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

26 16 8 18 0 0 28 35 8 6 31 16 5 3 20 0 0 0 0 0 0 0 5 0 9 6 6 21 20 6

0 2 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 4 1 0 0 0 0

2 0 2 0 0 0 0 1 0 0 0 0 0 0 85 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

11 41 4 11 0 16 3 6 8 7 23 26 24 21 0 1 31 5 5 7 5 0 17 14 0 0 0 0 1 5

1 0 0 1 0 3 0 1 1 0 1 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 77 1 0 0 4 0 4 0 0 0 0 0 0 1 0 1 0 5 2 1 0 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

keyword = $%&

(The Gospel of John, chapter 1) 1 In the beginning the Word already

existed. He was with God, and he was God. 2 He was in the beginning

with God. 3 He created everything there is. Nothing exists that he

didn't make. 4 Life itself was in him, and this life gives light to

everyone. 5 The light shines through the darkness, and the darkness

can never extinguish it. 6 God sent John the Baptist 7 to tell

everyone about the light so that everyone might believe because of

his testimony. 8 John himself was not the light; he was only a

witness to the light. 9 The one who is the true light, who gives

light to everyone, was going to come into the world. 10 But

although the world was made through him, the world didn't recognize

him when he came. 11 Even in his own land and among his own people,

he was not accepted. 12 But to all who believed him and accepted him,

he gave the right to become children of God. 13 They are reborn!

This is not a physical birth resulting from human passion or plan,

this rebirth comes from God.14 So the Word became human and lived

here on earth among us. He was full of unfailing love and

faithfulness. And we have seen his glory, the glory of the only

Son of the Father.

ans = ******


처음 세줄의 숫자들은 글자들의 돗수분포(histogram)입니다.  통계학적 방법으로 얻어진 keyword는 ***였습니다.  그리고 결과를 표시한 것입니다. 


아래는 제가 짠 소스코드입니다.


돗수분포를 저장하기 위해서 histo라는 변수를 만들었습니다.  일반적으로 ASCII 내에서만 쓴다면 128개만 저장해도 됩니다.


암호화키 길이에 따라서 돗수분포를 달리해줍니다.  암호화 키 길이가 무한대라면, 통계학적 방법에 의해서 암호를 해독하기 힘듭니다.  굉장히 많은 양의 동일암호로 작성된 암호화 문서가 필요합니다.  (이미테이션 게임이라는 영화를 보면 독일군 암호를 푸는 과정이 나오는데, 이 과정에서 암호화키를 찾아내는 알고리즘이 상당히 비슷합니다.)



다소 바보같은 모습의 주인공이고, 실제 당시의 내용과는 좀 다른 부분이 많았지만요.  재미있게 보았네요.  (아 옆길로 샜다.)


그리고 나서 guess 변수에 저장된 영문자들을 이용해서 암호화 키를 찾아내게 됩니다.



#include <stdio.h>
#include <memory.h>

int main()
{
    int histo[3][256];
    char cipher[] =
    {
        #include "p059_cipher.txt"
    };

    memset(histo, 0, sizeof(histo));
    for( int i = 0 ; i < sizeof(cipher) ; i++ )
        histo[i%3][cipher[i]]++;

    for( int i = 0 ; i < 3 ; i++ )
    {
        for( int j = 0 ; j < 128 ; j++ ) printf("%d ", histo[i][j]);
        putchar('\n');
    }

    char keyword[3] = { 0, 0, 0 };

    for( int i = 0 ; i < 3 ; i++ )
    {
        char *guess = " iaeocdghf";
        int maxh = histo[i][0];
        int maxv = 0;
        for( int j = 1 ; j < 128 ; j++ )
            if( maxh < histo[i][j] ) { maxh = histo[i][j]; maxv = j; }
        for( int j = 0 ; *(guess+j) ; j++ )
        {
            char s = *(guess+j)^maxv;
            if( s < 'a' || s > 'z' ) continue;
            int k;
            for( k = 0 ; k < 128 ; k++ )
            {
                if( histo[i][k] == 0 ) continue;
                if( (k^s) < ' ' || (k^s) > 'z' ) break;
            }
            if( k < 128 ) continue;
            keyword[i] = s;
            break;
        }
    }
    printf("keyword = %c%c%c\n", keyword[0], keyword[1], keyword[2]);
    int sum = 0;
    for( int i = 0 ; i < sizeof(cipher) ; i++ )
    {
        putchar(cipher[i]^keyword[i%3]);
        sum += cipher[i]^keyword[i%3];
    }
    putchar('\n');
    printf("ans = %d\n", sum);
}


저작자 표시 비영리 변경 금지
신고