프로그래밍/알고리즘

[프로젝트 오일러] Prob18

Nehoy 2017. 5. 20. 13:15
문제 사진 :



k층에서 k+1층으로 내려갈 때 큰 값으로만 내려가면 안된다. 왜냐하면 k+2층부터 n층까지가 변수가 되기 때문이다.
하지만, n-1층에서 n층으로 내려갈 때에는 변수가 될 층이 존재하지 않기 때문에 큰 값으로만 내려가면 된다. 

위 공식에 따르면, n-1층까지의 경로를 몰라도 n-1층의 한 노드에서 n층의 두 노드 중 어떠한 노드로 갈지는 알 수 있다.
이 n-1층부터 n층까지의 각각 모든 경로의 합을 n-1층에 저장해놓으면, n층의 데이터들은 쓸모가 없어지고 이것은 곧 n층이 사라졌다고 볼 수 있다.
따라서, n층의 삼각형이 n-1층의 삼각형이 된 것이다.
위 작업을 n - 1번 반복하면 삼각형 최상위 노드인 1층의 값이 이 문제에서 구하던 합이 최대가 되는 경로의 합이 된다.

// prob18.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
 
// argv[0] : (output) 배열 크기
// return : 동적할당된 배열
int **inputFile(int *_size) {
    FILE *pFile;
    int **arr, size;
    int i, j;
 
    pFile = fopen("input18", "r");
    if (pFile == NULL) {
        fprintf(stderr, "파일 열기 실패 - input\n");
        return NULL;
    }
 
    fscanf(pFile, "%d", &size);
    *_size = size;
 
    arr = malloc(sizeof(int *) * size);
    for (i = 0; i < size; i++) {
        arr[i] = malloc(sizeof(int) * (i + 1));
        for (j = 0; j <= i; j++)
            fscanf(pFile, "%d", &arr[i][j]);
    }
 
    return arr;
}
void release(int **arr, int size) {
    int i, j;
 
    for (i = 0; i < size; i++)
        free(arr[i]);
    free(arr);
}
 
int max(int num1, int num2) {
    return (num1 > num2) ? num1 : num2;
}
 
int main() {
    // 예제
    //    int arr[NUM][NUM] = {{3}, {7, 4}, {2, 4, 6}, {8, 5, 9, 3}}, temp[NUM - 1];
    //    int size = 4;
    int **arr, size;
    int i, j, sum;
 
    arr = inputFile(&size);
    if (arr == NULL) return -1;
 
    // 계산
    for (i = size - 2; i >= 0; i--) {
        for (j = 0; j <= i; j++)
            arr[i][j] += max(arr[i+1][j], arr[i+1][j+1]);
    }
 
    // 결과 출력
    printf("total sum : %d\n", arr[0][0]);
 
    // 할당 해지
    release(arr, size);
 
    return 0;
}

// input18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
15
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
 
cs

// 결과
total sum : 1074


저작자표시 (새창열림)