[ baekjoon ] #2630 색종이 만들기

백준 #2630 색종이 만들기

문제 요약

---

• 각 정사각형들은 하얀색 or 파란색으로 칠해져있음
• 전체 종이의 크기 → NxN(N=2k, k는 1 이상 7 이하의 자연수)
• 종이 자르는 규칙
  - 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 자름
  → 똑같은 크기의 네 개의 N/2 x N/2 색종이로 나눔
  - 모두 하얀색 or 파란색이거나 한 칸이 되어 더 이상 자를 수 없을 때까지 반복
• 잘라진 하얀색 색종이와 파란색 색종이의 개수 구하기 !

💡Idea

1. 색종이를 어떻게 계속 자를까?
   • for문을 돌면서 제일 첫 칸과 값이 다르면 break 후 재귀 호출
   • 다 같다면 해당 색종이 개수 증가 !

[ SourceCode ]

#include <iostream>
#include <vector>

#define white 0
#define blue 1

using namespace std;

int total_color[2]; // 각각의 종이 개수

void count_color(int x, int y, int N, vector<vector<int>> &paper) {
    int now = paper[x][y];
    bool flag = false;
    for(int i=x; i<x+N; i++) {
        for(int j=y; j<y+N; j++) {
            if(now != paper[i][j]) {
                flag = true;
                break;
            }
        }
        if(flag) break;
    }

    if(!flag) {
        if(now == white) total_color[white]++;
        else total_color[blue]++;
    }

    else {
        count_color(x, y, N/2, paper);
        count_color(x, y + N/2, N/2, paper);
        count_color(x + N/2, y, N/2, paper);
        count_color(x + N/2, y + N/2, N/2, paper);
    }

}

int main() {
    // 1. 입력받기
    int N; // 종이 크기
    cin >> N;
    vector <vector<int>> paper(N, vector<int>(N));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> paper[i][j];
        }
    }

    // 2. 각각의 색 개수 구하기
    count_color(0, 0, N, paper);

    cout << total_color[white] << endl;
    cout << total_color[blue] << endl;

    return 0;
}

Feedback

---

1. 시간초과가 발생하는 원인을 찾지 못해서 헤맸다,,
   • void count_color(int x, int y, int N, vector<vector<int>> paper)
     → vector를 값으로 넘기면 재귀 호출하면서 값을 복사하기 때문에 TLE 발생
   • void count_color(int x, int y, int N, vector<vector<int>> &paper)
     → vecotr를 참조로 넘기면 재귀 호출해도 TLE 발생 X