[백준,c++] 17136번 - 색종이 붙이기

문제

17136번: 색종이 붙이기

 

코드

#include <iostream>
#include <memory.h>

using namespace std;

int N = 10, ans = 1e9;
int map[10][10];
int paper_cnt;
int blank_cnt;
int paper_sum[6] = {5, 5, 5, 5, 5, 5};

bool paper_attach(int x, int y, int size){
    for(int i = x; i < x+size; i++){
        for(int k = y; k < y+size; k++){
            if(i >= 10 || k >= 10 || map[i][k] == 0) return false;
        }
    }
    for(int i = x; i < x+size; i++){
        for(int k = y; k < y+size; k++){
            if(map[i][k] == 1){
                blank_cnt--;
                map[i][k] = 0;
            }
        }
    }
    return true;
}

void backtracking(int x, int y){
    if(blank_cnt == 0){
        ans = min(ans, paper_cnt);
        return;
    }
    
    if(y == 10){
        x += 1;
        y = 0;
    }
    
    if(x == 10) return;
    
    int memory_arr[10][10];
    memcpy(memory_arr, map, sizeof(memory_arr));
    int memory_blank_cnt = blank_cnt;
    
    if(map[x][y] == 1){
        for(int i=5; i>=1; i--){
            if(paper_sum[i] > 0){
                if(paper_attach(x, y, i)){
                    paper_cnt++;
                    paper_sum[i]--;
                    backtracking(x, y + 1);
                    blank_cnt = memory_blank_cnt;
                    paper_sum[i]++;
                    paper_cnt--;
                    memcpy(map, memory_arr, sizeof(map));
                }
            }
        }
    }
    else backtracking(x, y+1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>map[i][k];
            if(map[i][k] == 1) blank_cnt++;
        }
    }
    
    backtracking(0, 0);
    
    if(ans == 1e9) cout<<-1;
    else cout<<ans;
}

 

풀이

문제를 대충 읽고.. 색종이를 5개씩 가지고 있다는 조건과, 0이 적힌 칸에는 색종이가 있으면 안 된다는 조건을 확인하지 못하고 풀어서 조금 헤매었습니다.

종이가 1인 좌표를 기점으로 백트랙킹을 도는데 항상 좌측 상단을 기준점으로 잡고 색종이를 붙여나가는 방식으로 구현했습니다. 

[백준,c++] 14712번 - 넴모넴모 (Easy)

위 문제의 풀이에서 색종이를 붙이는 조건만 구현해주면 됩니다.