[백준]색종이 붙이기

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

1.큰 종이부터 붙이면 되나보다 해서 큰종이 부터 붙였음.

2.반례가 있어서 작은종이로 오히려 더 작은 케이스를 만드는 경우가 있어서 5~1까지 종이의 사이즈를 바까주면서 붙임

3.반례 + 정례 를 해버리면 또 이상할거같아서 하나의 사이즈의 종이로 일률적으로 하는것은 아니라고 생각됨.

4.dfs를 통해 모든 조합을 통해 구해줘야할거 같음 ....ㅎ_ㅎ . 아래코드는 2번과정까지 ..

 

#include <iostream>
#include <cstring>
using namespace std;
 
/*
1.1x1~5x5 의 색종이를 5개씩 갖고 있다.
0~9 까지 가장 큰 색종이 부터 붙이면 될거같음. 
5개가 넘어가면 안된다.
조합으로 해야되나보다.... 하나의 크기로만 쭈루룩 해서는 안되는것같다.
*/
 
int map1[10][10];
int map[10][10];
int paper[6] = { 0,5,5,5,5,5 }; //색종이의 개수.
int ans = 0;
 
bool Check(int len,int r,int c) {
    bool flag = true;
    for (int i = r; i < r + len; i++) {
        for (int j = c; j < c + len; j++) {
            if (map[i][j] != 1) { flag = false; j = c + len; i = r + len; }
        }
    }
    return flag;
}
 
int main()
{    
    for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) cin >> map1[i][j];
    int mm = 1e9; //최솟값을 구해야함.
 
    for (int t = 5; t >= 1; t--) {
        //초기화
        memcpy(map, map1, sizeof(map));
        for (int i = 1; i <= 5; i++) paper[i] = 5;
        ans = 0;
 
        for (int l = t; l >= 1; l--) {
            //길이가 5인 색종이부터
            for (int r = 0; r <= 10 - l; r++) {
                for (int c = 0; c <= 10 - l; c++) {
                    if (Check(l, r, c) == true && paper[l] > 0) {
                        //붙일수 있다면
                        ans++; paper[l]--;
                        for (int i = r; i < r + l; i++) {
                            for (int j = c; j < c + l; j++) {
                                map[i][j] = l + 1;
                            }
                        }//붙이고 늘리기
                    }
                }
            }
        }
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (map[i][j] == 1) {
                    ans = 1e9; i = 10; j = 10;
                }
            }
        }
 
        if (mm >= ans) mm = ans;
    }
    //Show();
    if (mm == 1e9) { //값이 계속 바뀌지 않은경우 이렇게 처리하면 된다.
        printf("-1\n"); return 0;
    }
    printf("%d\n", mm);
    return 0;
}

 

완탐으로 마음을 비우고 다시 풀어봤다...

55%에서 계속 오답이 났었는데 조건하나를 추가해주니까 해결되었다... 1x1짜리를 붙일때가 문제였다.

 

맵의 크기가 10으로 고정되어있는데 범위검사를 안해주었다... 생각은 맵의 크기가 더 큰줄알고

뒤로가면 0을 만나서 자연스럽게 안붙이겠거니 생각했다.......

1.10으로 범위검사를 해주거나 2.맵을 그냥 16짜리 크기로 만드니까 통과했다...............

재귀는 재귀아래부분 부터의 논리적 흐름이 중요한거 같다... return 부분이 색다르고 어려웠다.

 

#include <iostream>
using namespace std;
 
int map[10][10];
int paper[6] = { 0,5,5,5,5,5 };
int ans = 1e9;
 
void dfs(int r, int cnt) {
    if (ans != 1e9 && cnt >= ans) return; //이미 더큰것은 할 필요가 없음(가지치기)
 
    for (int i = r; i < 10; i++) { //조합느낌으로 이미 붙인 행은 볼필요가 없다.(2차원 조합)
        for (int j = 0; j < 10; j++) {
 
            //전체를 돌면서 종이를 붙일수 있는지 확인
            if (map[i][j] == 1) {
                //1이 쓰여있으면 
 
                for (int l = 5; l >= 1; l--) {
                    //큰것부터 붙일수 있는지 확인
                    if (paper[l] <= 0 || l + i - 1 >= 10 || l + j - 1 >= 10) continue; //종이 없거나 범위 벗어나면 pass
                    bool flag = false;
                    for (int k = i; k < i + l; k++) {
                        for (int m = j; m < j + l; m++) {
                            if (map[k][m] == 0) { flag = true; k = i + l; m = j + l; }
                        }
                    }
                    if (flag == true) continue;// 못붙이면 다음으로 pass
                    
                    //dfs
                    paper[l]--;
                    for (int k = i; k < i + l; k++) {
                        for (int m = j; m < j + l; m++) {
                            map[k][m] = 0;//붙이기
                        }
                    }
                    dfs(i, cnt + 1);
                    paper[l]++;
                    for (int k = i; k < i + l; k++) {
                        for (int m = j; m < j + l; m++) {
                            map[k][m] = 1;//떼기
                        }
                    }
                }
 
                //여기까지왔다는것은 1이 있지만 붙이지 못했다는 것(실패)
                return;
            }
 
            if (i == 9 && j == 9) {
                //모든 종이를 탐색했지만 실패 하지 않았다는 것
                if (ans >= cnt) ans = cnt;
            }
        }
    }
}
 
int main()
{
    for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) cin >> map[i][j];
    dfs(0, 0);
    printf("%d\n", ans == 1e9 ? -1 : ans);
    return 0;
}