본문 바로가기
Programming/Project Euler

프로젝트 오일러 #67 최대 경로의 합

by 작은별하나 2016. 6. 30.
반응형

난이도는 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]);
}

 

댓글