난이도는 5%로 별로 높지 않은 문제입니다.


그러나 A* 알고리즘 등 기초 알고리즘을 이용해서 짤 수 있는 문제이고, 또, 많은 게임 프로그램에서 활용 가능한 문제입니다.


Maximum path sum II


어떤 한 곳에서 갈 수 있는 길은 2가지이므로, 높이가 10이면, 2의 9승인 512가지의 길이 존재합니다.  이 길 중 상당부분은 부분경로가 같기 때문에, 이러한 경로의 합을 구하는 방법으로는 동적프로그래밍(dynamic programming)이라는 알고리즘 기법을 이용해서 풀면 좋습니다.


동적 프로그래밍은 메모리를 추가로 사용해야 하지만, 저는 그냥 기존의 데이터 저장공간을 그대로 사용했습니다.  그렇게 하여도 큰 문제가 없겠죠.  중간에 한 지점에 대해서 올 수 있는 경로는 최대 2가지입니다.  그 2가지 경로중 최대값을 택해서 본인의 최대값을 적으면 됩니다.


위에서부터 내려와도 되겠지만, 제 경우에는 아래로부터 위로 올라가게 하였습니다.  왜냐하면 루트 한점에서 바로 값을 찾고 싶어서였습니다.  당연히 마지막 줄은 따로 계산할 필요가 없이 해당 지점의 값이 최댓값입니다.  이렇게 하면 위에서 내려오는 것보다 아래에서 위로 가는 것이 계산량도 더 적습니다.


아래의 코드는 제가 작성한 것입니다.  참고용으로만 써주세요.



#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define FN  "p067_triangle.txt"

int main()
{
    uint64_t h[16384];
    int n = 0;
    char s[4096];

    FILE *fi = fopen(FN, "r");
    while( fgets(s, 4096, fi) )
    {
        for( char *tok = strtok(s, " \r\n") ; tok ; tok = strtok(0, " \r\n") )
            h[n++] = atoi(tok);
    }
    fclose(fi);

    printf("n = %d\n", n);

    for( int d = sqrt(2*n)-2; d >= 0 ; d-- )
    {
        int s = d*(d+1)/2;
        int t = (d+1)*(d+2)/2;
        for( int i = 0 ; i < t ; i++ )
        {
            int l = t+i, r = t+i+1;
            h[s+i] += (h[l]>h[r])?h[l]:h[r];
        }
    }

    printf("Ans = %ju\n", h[0]);
}


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



제곱수 문제이긴 하지만, 의외로 이 문제는 쉽습니다.  난이도도 5%입니다.



그냥 단순 무식하게 풀어도 이 문제는 큰 하자가 없습니다.  일단, 제곱을 할 수는 10 미만의 수입니다.  10의 n제곱수는 자릿수로는 n+1자리가 되기 때문이죠.  당연히 10보다 큰 수는 말할 것도 없겠죠.


그러니 1에서 9까지 제곱해가면서 자릿수 계산하시면 됩니다.  오버플로우만 조심하면 별 문제 없을겁니다.


2를 제곱해서, 과연 얼마나 많은 같은 제곱자리수를 얻을 수 있을까요.  간단하게, 2의 1제곱하면 2이니까, 하나는 만족합니다.  2의 2제곱은 4이니까, 그 후는 볼 것이 없겠죠.  그래서 2로 만들 수 있는 최대 갯수는 1입니다.  저는 이것을 식으로 다음과 같이 표현했습니다.



n이 1이라면 저 값은 1이 되겠죠. n이 2라면 약 1.43으로 역시 1이 됩니다.  n이 3이라면 1.912 정도로 역시 1입니다.  3의 제곱하면 9이니까, 거의 10에 가깝죠.  n이 4라면, 2.51정도로 2가 되는 것을 알 수 있습니다.  4의 제곱은 16으로, 처음으로 제곱수가 두자릿수가 됩니다.  이렇게 계산을 하면 손으로도 얼마든지 계산을 할 수가 있습니다.


제가 작성한 코드는 다음과 같습니다.



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

void solve1()
{
    int count = 1;
    for( int i = 2 ; i < 10 ; i++ )
    {
        count += 1.0/(1.0-log10((double)i));
    }
    printf("Ans = %d\n", count);
}

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



이번 문제는 난이도 15% 문제네요.


저는 의외로 쉽게 풀었습니다.  (단순무식법으로요.)



서로 다른 세제곱수 5개가 같은 숫자들로 이루어진 경우 그 중 가장 작은 수를 구하라는 문제입니다.


사실 이 문제를 정석적으로 푼다면, 정확하게 5개가 나오는지 검사해야 하지만, 저는 그것까지는 검사하지 않았습니다.


또한 같은 숫자가 4개 이상 나오는 것도 배제했습니다.  사실 그러면 안 되지만, 배열에다가 데이터를 저장하는 방식을 이용하다보니, 같은 숫자가 4개 이상 나오면 안 되어서요.  해시를 쓰면 좀 더 나으려나요.  그러면 자릿수가 6자리인것, 7자리인것, .. 형태로 정확하게 5개가 나오면서, 같은 숫자가 4개 이상 나오는 것도 허용할 수 있었을텐데요.  그치만 복잡한 자료구조 쓰는 것을 귀찮아해서요.  (아무래도 기본적으로 STL이나 제공되는 자료구조가 없다면 잘 안 쓰게됩니다.)


아래는 제가 작성한 프로그램입니다.



#include <stdio.h>
#include <time.h>
#include <stdint.h>

int index(int64_t n)
{
    int cnt[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    while( n )
    {
        cnt[n%10]++;
        n /= 10;
    }
    int idx = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( cnt[i] >= 4 ) return 0;
        idx <<= 2;
        idx |= cnt[i];
    }
    return idx;
}

void solve1()
{
    static int count[1<<20], value[1<<20];

    for( int i = 300 ; ; i++ )
    {
        int64_t cube = (int64_t)i*i*i;
        int idx = index(cube);
        if( idx == 0 ) continue;
        if( count[idx] == 4 )
        {
            int64_t v = value[idx];
            printf("Ans = %lld(%lld)\n", v*v*v, v);
            break;
        }
        if( count[idx] == 0 ) value[idx] = i;
        count[idx]++;
    }
}

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