[백준] 17136 색종이 붙이기

 

그리디로 푸는 너무 쉬운 문제인 줄 알고 한대맞은 문제다

A형 기출 문제니까 보기 쉽게 함수를 좀 많이 짜놨따

 

먼저 푸는 방법을 생각해보자

1. (0,0) ->(10,10) 까지 한칸씩 차례로 본다

2. 내 현재 위치의 값이 0이라면 => 다음칸으로 간다

3. 내 현재 위치가 1이라면

   3-1) 종이로 덮어야하므로 종이가 몇개남았는지본다

   3-2) 이 때 모든 경우 다 보니까 최대한 빠르게 큰 것부터 덮어보자

   3-3) 해당 종이가 아직 남아있다면 can_cover를 통해 덮을 수 있는지 확인

   3-4) 덮을 수 있으면 현재 종이로 덮는 위치를 임시변수에 저장시키고

   3-5) 종이로 덮은 후 (pos+1,cnt+1)로 다음칸으로 덮은 종이 수를 올리고 떠나자

   3-6) 끝난 후에는 다시 원래대로 돌려준다

4. 모든 경우를 이렇게 다 보면서 답을 찾자

 

여기서 pos를 통해 1칸씩 움직였다

[10][10]의 2차원 배열이지만 사실 arr[100] 인 1차열과 똑같다

x와y는 pos/10, pos%10으로 각각 구해줄 수 있다

내가 마지막칸을 지난 100 까지 온다면 다 덮었다는 얘기이므로 답을 찾을 수 있다

 

조금 힘들게 풀었다.. 연습을 해야겠다

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int paper[6] = { 0,5,5,5,5,5 };
int map[11][11];
int temp[11][11];
int ans = 1e9;
bool inner(int x, int y) {
    return (0 <= x && x < 10 && 0 <= y && y <10);
}
bool can_cover(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (!inner(i,j) || !map[i][j]) return false;
        }
    }
    return true;
}
 
void save_map(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            temp[i][j] = map[i][j];
        }
    }
}
 
void cover(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            map[i][j] = 0;
        }
    }
}
 
void origin(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            map[i][j] = temp[i][j];
        }
    }
}
 
void solve(int pos, int cnt) {
    if (pos == 100) {
        ans = min(ans, cnt); return;
    }
    int x = pos / 10,y = pos % 10;
 
    if (!map[x][y]) solve(pos + 1, cnt);
    else {
        for (int i = 5; i >= 1; i--) {
            if (!paper[i] || !can_cover(x,y,i)) continue;
            paper[i]--;
            save_map(x, y, i);
            cover(x, y, i);
            solve(pos + 1, cnt + 1);
            origin(x, y, i);
            paper[i]++;
        }
    }
}
 
int main() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf(" %d", &map[i][j]);
        }
    }
    solve(0, 0);
    printf("%d\n", (ans == 1e9) ? -1 : ans);
}