Problem 11 : Largest product in a grid (5%)

Description

original

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

간략해석

다음 표에서 대각선 곱 중 가장 큰 값을 찾으시오.

Idea & Algorithm

naive idea

반복문으로 4방향에 대해서 찾으면 된다. 조건문과 반복문으로 모서리 처리를 해주면 된다.

advanced idea

배열을 4칸씩 미루게 된다면, 예외처리를 할 필요 없이 모든 예외값들이 0으로 변환가능하다. 또한 조건문 대신 방향벡터를 사용한다면 반복문으로 쉽게 처리할 수 있다.

source code

#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)

int arr[28][28];
int dx[4] = {0,1,1,1}, dy[4] = {1,-1,0,1};

int main(){
    int maxnum = 0;
    for(int i = 4 ; i <= 23 ; i++){
        for(int j = 4 ; j <= 23 ; j++){
            scanf("%d",&arr[i][j]);
        }
    }
    for(int i = 4 ; i <= 23 ; i++){
        for(int j = 4 ; j <= 23 ; j++){
            for(int k = 0 ; k < 4 ; k++){
                int tmp = arr[i][j];
                for(int w = 1 ; w <= 3 ; w++){
                    tmp * = arr[i+w*dx[k]][j+w*dy[k]];
                }
                maxnum = MAX(maxnum,tmp);
            }
        }
    }
    printf("%d",maxnum);
}

Problem 011