코테 일기(10) : 백준 [1051번] 숫자 정사각형

DP(Dynamic Programming)를 풀다가 머리가 아파서 잠깐 brute force로 돌렸다...

역시 어려운 것을 하다가 쉬운 것을 풀면 너무 빨리 풀린다.

총 코딩 시간 10분, 삽질 20분...

정답률 37%는 아무래도 오답을 했던 기록까지 포함해서 인지 상당히 낮다. 

하지만 난이도는 초보자도 풀 수 있을 정도라는 것. (전형적인 brute force 문제이다.)

코드

#include <iostream>

#include <vector>

#include <stdio.h>

 

using namespace std;

 

int find_square(vector<vector<int> > arr) {

        int result = 1;

        for (int i = 0; i < arr.size(); i++) { // 행 위치

                 for (int j = 0; j < arr[0].size(); j++) { // 열 위치

                                 for (int k = 1; k < arr[0].size() - j && k < arr.size() - i; k++) { 

//k가 표를 벗어나지 않는 범위에서

 

                                          if (arr[i][j] == arr[i + k][j + k] &&

                                                  arr[i][j] == arr[i + k][j] &&

                                                  arr[i][j] == arr[i][j + k]) { 

    //k의 거리만큼 있는 꼭짓점이 모두 같을때

                                                  //대각선, 오른쪽, 아래를 검사

                                                  result = result > (k + 1)*(k + 1) ? result : (k + 1)*(k + 1); 

//k가 변의 길이이므로 k를 제곱시킨다

                                          }

                                 }

                        

                 }

        }

                 return result;

}

 

int main() {

        int N, M;

        cin >> N >> M;

        vector<vector<int> > arr(N, vector<int>(M, 0));

 

        for (int i = 0; i < N; i++) {

                 for (int j = 0; j < M; j++) {

                         scanf("%1d", &arr[i][j]);

                 }

        }

        cout << find_square(arr);

}

 

 

나를 당황하게 만들었던 것은 처음 제출 했을 때였다. 

틀렸기에 설마 0으로 이루어진 정사각형은 포함하지 않는 것인가?

라는 생각이 들었고 0이 큰 원소만 찾도록 코드를 고쳤었다.

하지만 큰 착각이었고 문제는 

 if (arr[i][j] == arr[i + k][j + k] &&  arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i][j + k])

이었고 문제는 이들을 모두 '=='으로 한 번에 사용할 수 가 없었다는 것이다.

이걸 발견하지 못하고 애꿎은 표만 붙잡고 있었으니...

결과