[C++]프로젝트 오일러 11번 문제&풀이 (20×20 격자에서 연속된 네 수의 곱 중 최댓값)

문제

아래와 같은 20×20 격자가 있습니다.

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

위에서 대각선 방향으로 연속된 붉은 수 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.

그러면 수평, 수직, 또는 대각선 방향으로 연속된 수 네 개의 곱 중 최댓값은 얼마입니까?

 

접근방법

1. 이 문제는 띄어쓰기로 구분된 격자 형태의 자료를 어떻게 읽어 들이는지가 문제의 핵심이다. 수기로 숫자 사이에 콤마( , )를 입력하는 방식이 있겠으나, 문제 취지에 맞게 최소한 데이터를 건드리지 않는 방법을 찾아보았다.

   ( 20X20 형태로 되어 있는 문제, 띄어쓰기로 구분되어 있는 문제, 한자리 숫자들은 03, 09, 01, 00 와 같이 설정되어 있는 문제 해결 필요!)

 

2. 일단 string(str)에 집어 넣고, istringstream과 getline을 이용하여 띄어쓰기를 구분자로 하여 벡터(string_vec)에 저장해 준다. 

 

3. 그다음, stoi를 이용하여 string(string_vec)에서 int(int_array[20][20])로 형 변환을 해준다.

   (동시에 벡터에서 이차원 배열(int_array[20][20])로 저장해준다.)

 

4. 여기부터는 가로로 연속된 네개의 수, 세로로 연속된 네개의 수, 대각선으로 연속된 수의 네개의 곱을 구하여 벡터(square_vec)에 저장해 준다.

 

5. 이 중에서 가장 큰 값을 구하면 끝!

 

 

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

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

    while (getline(str_string, stringBuffer, ' '))
    {
        string_vec.push_back(stringBuffer);
        //cout << stringBuffer << " ";
    }

    /*for (int n = 0; n < string_vec.size(); n++)
    {
        cout << string_vec[n] << " ";       
    }
    cout << endl;*/

    int int_array[20][20];
    int k = 0;

    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            int_array[i][j] = stoi(string_vec[k]);
            k++;
            //cout << int_array[i][j] << ' ';
        }
        //cout << endl;
    }

    vector<long> square_vec;
    int l = 0;
    long max_value = 0;
    square_vec.clear();

    //horizontal
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 17; j++)
        {
            square_vec.push_back(int_array[i][j] * int_array[i][j+1] * int_array[i][j+2] * int_array[i][j+3]);
            //cout << square_vec[l] << endl;
            max_value = max(max_value, square_vec[l]);
            l++;
        }
        //cout << endl;
    }

    //Vertical
    for (int j = 0; j < 20; j++)
    {
        for (int i = 0; i < 17; i++)
        {
            square_vec.push_back(int_array[i][j] * int_array[i + 1][j] * int_array[i + 2][j] * int_array[i + 3][j]);
            //cout << square_vec[l] << endl;
            max_value = max(max_value, square_vec[l]);
            l++;
        }
        //cout << endl;
    }

    //diagonal 1
    for (int i = 0; i < 17; i++)
    {
        for (int j = 0; j < 17; j++)
        {
            square_vec.push_back(int_array[i][j] * int_array[i + 1][j + 1] * int_array[i + 2][j + 2] * int_array[i + 3][j + 3]);
            //cout << square_vec[l] << endl;
            max_value = max(max_value, square_vec[l]);
            l++;
        }
        //cout << endl;
    }

    //diagonal 2
    for (int i = 0; i < 17; i++)
    {
        for (int j = 3; j < 20; j++)
        {
            square_vec.push_back(int_array[i][j] * int_array[i + 1][j - 1] * int_array[i + 2][j - 2] * int_array[i + 3][j - 3]);
            //cout << square_vec[l] << endl;
            max_value = max(max_value, square_vec[l]);
            l++;
        }
        //cout << endl;
    }

    cout << "Answer is : " << max_value << endl;

    return 0;
}

 

참고

 

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler