Written by JS970
on March 21, 2023

2630 - 색종이 만들기

난이도: 실버 2
날짜: 2023년 3월 21일
상태: Correct
추가 검토 여부: No
알고리즘 : Divide and Conquer

Solution

분할정복을 활용한 recursion을 통해 문제의 요구대로 구현하였다.
2차원 배열을 계속해서 생성할 수 없으므로 원본 배열에서 왼쪽 위의 인덱스를 넘기는 방식으로 subarray에 대한 순회를 구현했다.
pair를 사용하여 흰 종이와 파란색 종이의 개수를 셌다.
2차원 배열 구간 순회의 인덱싱에 있어 숙련도가 부족해 틀린 답이 계속 출력되었다.
- 아래 코드에서 top은 column을, left는 row를 의미했는데, 변수명이 애매해서 계속 했갈렸다.
- 앞으로는 col, row등의 표현을 사용하는 것이 좋을 것 같다.
- 아래와 같은 할당에서 배열은 좌표평면의 제 4사분면 방향임을 명심하자
- sameColor함수의 for문에서 i, j의 반복문 탈출 조건을 잘못 설정하여 틀렸었다.
- count함수의 recursion부분에서 N/div라고 표기하지 않고 단순히 N/2라고 적어 틀렸었다.

code

#include <iostream>
#include <utility>
using namespace std;

bool sameColor(int ** arr, int left, int top, int div, int N)
{
    bool comp = arr[top][left]; 
    for(int i = top; i < N/div + top; i++)
    {
        for(int j = left; j < N/div + left; j++)
        {
            if(arr[i][j] != comp) return false;
        }
    }
    return true;
}

pair<int,int> count(int ** arr, int left, int top, int div, int N)
{
    if( sameColor(arr, left, top, div, N) )
    {
        if (arr[top][left] == 1) return make_pair(0, 1);
        else return make_pair(1, 0);
    }
    else
    {
        div *= 2;
        pair<int, int> lt = count(arr, left, top, div, N);
        pair<int, int> rt = count(arr, left + (N/div), top, div, N);
        pair<int, int> lb = count(arr, left, top + (N/div), div, N);
        pair<int, int> rb = count(arr, left + (N/div), top + (N/div), div, N);
        return make_pair((lt.first + rt.first + lb.first + rb.first), (lt.second + rt.second + lb.second + rb.second));
    }
}

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

    pair<int, int> print = count(arr, 0, 0, 1, N);
    cout << print.first << " " << print.second << endl;
    return 0;
}

기초 C++ array 확인 코드 ^___^

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int ** array = new int*[N];

    /*
        < 2 - dimentional array, index : [i][j] >
        --> direction of j (row)
        *---*---*---*---*  | direction of i (column)
        |0,0|0,1|0,2|0,3|  v
        *---*---*---*---*
        |1,0|1,1|1,2|1,3|
        *---*---*---*---*
        |2,0|2,1|2,2|2,3|
        *---*---*---*---*
        |3,0|3,1|3,2|3,3|
        *---*---*---*---*
    */

    // dynamic allocation of 2-dimentional array(size N*N)
    for(int i = 0; i < N; i++)
    {
        // dynamic allocation of row
        array[i] = new int[N];
        for(int j = 0; j < N; j++)
            cin >> array[i][j];
    }
    cout << "==================\n";

    // print allocated array
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            cout << array[i][j] << " ";
        cout << endl;
    }
    cout << "==================\n";

    // print each element
    cout << "array[2][2] : " << array[2][2] << " == (2*N) + 2 == (i*N) + j" << endl;
    cout << "array[2][3] : " << array[2][3] << " == (2*N) + 3 == (i*N) + j" << endl;
    cout << "array[3][2] : " << array[3][2] << " == (3*N) + 2 == (i*N) + j" << endl;
    cout << "array[7][7] : " << array[7][7] << " == (7*N) + 7 == (i*N) + j" << endl;

    return 0;    
}

ref

2630번: 색종이 만들기

Top