코테 일기(11) : 백준 [1780번] 종이의 개수

전형적인 divide and conquer 문제이다.

코드를 짜는데 30분 밖에 걸리지 않았지만, 그 놈의 시간초과 때문에 한참을 애썼다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <vector>

#include <iostream>

 

using namespace std;

 

int pr[3]; //pr[0] -> -1, pr[1] -> 0, pr[2] -> 1

vector<vector<int> > input; //입력 받을 배열

 

typedef struct {

        int row;

        int col;

} place;

void div_paper(int param, place pl) {//배열과 배열 크기, 위치를 인자로 넣음

 

        if (param == 1) { //크기가 1개면 바로 return 할 수 있게 함.

                 if (input[pl.row][pl.col] == 1) {

                         pr[2] += 1;

                 }

                 else if (input[pl.row][pl.col] == 0) {

                         pr[1] += 1;

                 }

                 else if (input[pl.row][pl.col] == -1) {

                         pr[0] += 1;

                 }

                 return;

        }

 

        for (int i = pl.row; i < pl.row + param; i++) { //행 범위

                 for (int j = pl.col; j < pl.col + param; j++) { //열 범위

                         if (input[pl.row][pl.col] != input[i][j]) { //다른 값이 존재하면

                                 int next_param = param / 3; //Delimiter

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

                                                  for (int j = 0; j < 3; j++) { //9만큼 수행

                                                       div_paper(next_param, { pl.row + (next_param*i),pl.col + (next_param*j) });

                                                          //재귀

                                                  }

                                          }

                                          return;

                         }

                 }

        }

        if (input[pl.row][pl.col]==1) {

                 pr[2] += 1;

                 return;

        }

        if (input[pl.row][pl.col]==0) {

                 pr[1] += 1;

                 return;

        }

        if (input[pl.row][pl.col]==-1) {

                 pr[0] += 1;

                 return;

        }

 

       

        return;

}

int main() {

        int num = 0;

        scanf("%d", &num);

        place pl = { 0,0 }; //위치

        input.resize(num, vector<int>(num, 0));

 

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

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

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

                 }

        }

 

        div_paper(num, pl);

 

        printf("%d\n%d\n%d", pr[0], pr[1], pr[2]);

}

 

항상 전역변수를 사용하지 않으려는 습관을 들여왔었다.

하지만 알고리즘은 코딩 스타일이 아닌 문제 해결 능력을 보는 것이라는 점.

메모리가 많이 주어졌기 때문에, 문제를 푸는 입장에서는 Memory leak을 전혀 걱정할 필요가 없다.

앞으로 알고리즘에서는 전역변수를 좀 사용해야겠다.

(기존에는 배열 parameter를 div_paper 함수에 추가해 재귀시켰다. 

하지만 전역변수를 사용하고 나서부터는 파라미터가 절반으로 줄었다.)

결과

다음은 메모리가 아닌 시간 초과를 고려하여 작성을 하면 조금 더 빨리 끝날 것 같다.