[알고리즘] 백준 17136

백준 17136번 색종이 붙이기

해결 과정 요약

남은 종이 개수를 저장할 paper 배열 선언, 사용한 종이의 최솟값을 저장할 min_cnt 선언.
canAttach, attach, detach 함수 만들고,
붙이고 탐색하고 떼고를 반복할 go 함수를 만든다.
탐색중 min_cnt보다 cnt가 커지면 탐색중단하고 탐색이 끝나면 min_cnt를 최신화 시켜준다.

풀이

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int min_cnt = 30;
int paper[6] = {5, 5, 5, 5, 5, 5};
int m[10][10];

bool canAttach(int y, int x, int width){
    if(y + width > 10 || x + width > 10) return false;
    if(paper[width] == 0) return false;
    if(m[y][x] == 0) return false;
    for(int i=0; i<width; i++){
        for(int j=0; j<width; j++){
            if(m[y+i][x+j] == 0) return false;
        }
    }
    return true;
}

void attach(int y, int x, int width){
    for(int i=0; i<width; i++){
        for(int j=0; j<width; j++){
            m[y+i][x+j] = 0;
        }
    }
    paper[width]--;
}

void detach(int y, int x, int width){
    for(int i=0; i<width; i++){
        for(int j=0; j<width; j++){
            m[y+i][x+j] = 1;
        }
    }
    paper[width]++;
}

void go(int y, int x, int cnt){
    if(cnt >= min_cnt) return;
    if(x == 10){
        go(y + 1, 0, cnt);
        return;
    }
    if(y == 10) {
        min_cnt = min(min_cnt, cnt);
        return;
    }
    if(m[y][x] == 0){
        go(y, x + 1, cnt); return;
    }
    for(int width = 5; width > 0; width--){
        if(canAttach(y, x, width)){
            attach(y, x, width);
            go(y, x + width, cnt + 1);
            detach(y, x, width);
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin >> m[i][j];
        }
    }
    go(0, 0, 0);
    if(min_cnt == 30) cout << "-1";
    else cout << min_cnt;
    
    return 0;
}

트러블슈팅

완전탐색에 익숙하지 않아서 go함수를 만드는데 시간이 오래걸렸다.

코멘트

여러가지 조건들이 많아서 변수와 함수를 어떻게 만들고 쓸지 고민이 많았던 문제.