[백준] 2630번 - 종이의 개수

[2630] 종이의 개수

[Baekjoon 문제 링크]

재귀를 사용하는 문제인 2630번을 풀어보았다.

 

 

우선 종이를 자르는 함수(재귀 함수)를 만들어야 하는데, 나는 cutPaper라는 이름으로 만들었다.
cutPaper 함수 안에서는 종이를 구성하는 숫자가 모두 동일한지 확인하여 아래와 같이 처리해줘야 한다.

• 종이가 모두 같은 수로 되어 있는 경우(same) : 종료 조건이다. 빈도수만 증가시킨 후 return한다.
• 같은 수로 되어 있지 않은 경우(!same): 현재의 색종이를 4분할 한 후(행 2등분, 열 2등분) 각각에 대해 다시 cutPaper 함수를 호출한다.

 

자세한 구현 아이디어는 아래 글에 작성해 놓았다. 코드가 진짜 똑같아서 구현 아이디어도 완전 동일하다. 단 분할 개수만 다르다! (아래 글의 문제는 9등분이다. )

2024.10.11 - [분류 전체보기] - [재귀] 백준 1780번 - 종이의 개수

 

코드 설명

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [N, ...paper] = fs.readFileSync(path).toString().trim().split('\n').map(row => row.split(' ').map(Number));


let answer = [0, 0]; //answer[0] : 0의 빈도수 / answer[1] : 1의 빈도수

const cutPaper = (rowStart, colStart, size) => {

    // 색종이 왼쪽 위 꼭짓점의 인덱스
    const first = paper[rowStart][colStart];
    let isSame = true;

    // 색종이 안에 있는 모든 숫자를 확인하며
    for(let r = rowStart; r < rowStart + size; r++ ){
        for(let c = colStart; c < colStart + size; c++) {
            // 하나라도 첫 번째 요소와 다른게 있다면, isSame은 false
            if(first !== paper[r][c]) {
                isSame = false;
                break;
            }
        }
        if(!isSame) {
            break;
        }
    }    

    if (isSame) { //모든 요소가 같다면? -> 종료 조건

        // 색종이 종류 확인 후 빈도수 증가 (-1인지, 0인지, 1인지)
        answer[first]++;
        return;
    } else {

        // 4개의 색종이를 만들어 cutPaper 다시 호출!
        size /= 2; //자르니까 가로,세로 모두 1/2 사이즈가 된다.
        for(let i = 0; i < 2; i++) {
            for(let j = 0; j < 2; j++) {
                cutPaper(rowStart + i * size , colStart + j * size, size);
            }
        }
    }
};

cutPaper(0, 0, N);
console.log(answer.join('\n'));

이 문제 풀 수 있으면 1780, 1992는 코드 복붙해서 좀만 수정하면 풀 수 있다. 완전 럭키비키쟈나🍀