baekjoon - (색종이 만들기)

알고리즘 문제/분할정복

baekjoon - (색종이 만들기)

재밌는게임~ 2024. 8. 14. 12:21

문제 번호 : 2630번

난이도 : Silver 2

시간 제한메모리

1 초

128 MB

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

예제 입력 1 복사

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

예제 출력 1 복사

9
7

풀이)

이 문제는 해당 배열을 분할하여 1과 0을 카운트 해주면 된다.

자세히 알아보자

먼저 분할 정복이라는 알고리즘은 엄청나게 크고 방대한 문제를 용이하게 풀 수 있는 문제 단위로 나눈다이다.

조금 더 쉽게 설명하면

분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.

정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.

조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

이렇게 말할 수 있겠다.

그러면 분할정복은 알아봤으니 풀이과정을 설명하겠다.

1. 분할정복의 함수를 만든다.

2. 함수의 매개변수는 현재 Y위치, 현재 X위치, 길이를 받는다.

3. 함수 내 첫 코드는 길이가 1일때는 더 이상 분할을 할 수 없기 때문에 함수를 나가야한다,.

"문제에서는 블루 종이와 흰색 종이의 갯수를 판단하는 거니까 현재 길이가 1일때 현재 내위치에 있는 종이가 1인지 0인지를 판단하여 Count를 증가시켜준다."

4. 그리고 다음은 분할이 가능한 상태라면 현재 내 위치에 있는 1또는0인 값과 현재 내위치에서 길이만큼 가는 동안 현재 내위치에 있던 값과 동일한지 판단하는거다.

"만약

1101

0011

이라는 배열이 있을 때 x가 2만큼 y가 2만큼의 값이

11 00

11 이면 이 색종이는 1개라고 친다. 00 도 마찬가지이다.

그러면 이 색종이는 분할 할 필요가 없는 것이다.

5. 여기까지 왔으면 분할 할 수 있는 상태이다.

6. curY, curX, length로 4등분으로 분할하면 분할한 함수에서 다시 지금까지의 과정을 거치면서 분할을 수행한다.

코드)

#include <bits/stdc++.h>
using namespace std;
int arr[129][129];
int blueCount = 0;
int whiteCount = 0;
void DevideAndConquer(int curY, int curX, int length){
    if(length == 1){
        if(arr[curY][curX] == 1){
            blueCount++;
        }else{
            whiteCount++;
        }
        return;
    }
    bool isSame = true;
    int sample = arr[curY][curX];
    for(int y=curY; y<curY+length; y++){
        for(int x=curX; x<curX+length; x++){
            if(arr[y][x] != sample){
                isSame = false;
            }
        }
    }
    if(isSame){
        if(sample == 1){
            blueCount++;
        }else{
            whiteCount++;
        }
        return;
    }

    DevideAndConquer(curY, curX, length/2);
    DevideAndConquer(curY, curX+length/2, length/2);
    DevideAndConquer(curY+length/2, curX, length/2);
    DevideAndConquer(curY+length/2, curX+length/2, length/2);
}
int main() {
    int N;
    cin >> N;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> arr[i][j];
        }
    }

    DevideAndConquer(0, 0, N);

    cout << whiteCount << "\n";
    cout << blueCount << "\n";
    return 0;
}

728x90

저작자표시 비영리 동일조건 (새창열림)