[c++] 백준 2630 - 색종이 만들기(분할 정복)

0. [c++] 백준

https://www.acmicpc.net/problem/2630

1. 풀이

분할 정복의 기초같은 문제였다.

이번 문제에서 주어진 범위 내 중복되지 않는 원소가 있는 경우 이 범위를 4분할 해야 했다.

따라서 이를 함수로 만들어 재귀적으로 해결하게 구현하였다.

처음에 함수를 pair로 선언해 문제를 해결하려 하였지만, 쓸때없는 낭비인 것 같아서 결과를 따로 전역변수로 선언해주었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include<iostream>   using namespace std;   int arr[130][130]; pair<int, int> ret;   void calc(const int& here_y, const int& here_x, const int& length) {     int here_num = arr[here_y][here_x];       //기저 사례 : 길이가 1인 경우     if (length == 1) {         if (arr[here_y][here_x] == 0) {             ret.first++;             return;         }         else {             ret.second++;             return;         }             }       bool check = true;     for (int y = here_y; y < here_y + length; y++) {         for (int x = here_x; x < here_x + length; x++) {             if (arr[y][x] != here_num) {                 check = false;                 break;             }         }         if (!check)             break;     }       if(check)         if (arr[here_y][here_x] == 0) {             ret.first++;             return;         }         else {             ret.second++;             return;         }     else {         int next_lenght = length / 2;         calc(here_y, here_x, next_lenght);         calc(here_y + next_lenght, here_x, next_lenght);         calc(here_y, here_x + next_lenght, next_lenght);         calc(here_y + next_lenght, here_x + next_lenght, next_lenght);     } }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;     for (int y = 0; y < N; y++) {         for (int x = 0; x < N; x++) {             cin >> arr[y][x];         }     }       calc(0, 0, N);       cout << ret.first << "\n" << ret.second; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!