17136 c++

1. 핵심적으로 55부터 먼저 가능하면 덮어쓰는 형식으로 가면 안된다, 왜냐하면 44를 놓는것이 답일수도 있기때문
2. 그러면 결국 1을 만났을때 5칸 4칸,3칸,,,이런식으로 전부 확인을 해야한다는점. -> 여기서 재귀를 써야한다는것을 판단.
3. 재귀호출시 항상 0~10까지로 범위를 설정 왜냐하면, 그래야 그다음 1을 찾을 수 있기 때문
4. 만약 if문을 넣고 끝나면 반드시 return을 넣을것 이게 분할정복에 해당하는, 2630문제와 동일한데, return을 안넣으면 무한루프에 빠질수있음 왜냐하면 그림과 같이 2,2을 덮고 0인걸 1로 복구했다 치자 그러면 재귀니까 마지막으로 호출된 0,0으로 가게되고 여기서 이중포문을 탈출하지 못했다면, for문을 돌아 2,2의 1을 덮어쓰러 가야하기 때문이다.
5. 마지막으로 시작점이 좌표로 주어진경우 i=x, x+k(이동할좌표) 이런식으로 쓰면된다.

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

int Answer = 999999;
int map[10][10];
int paper[5] = { 5,5,5,5,5 };

void init() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
		}
	}
}

bool one_left() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j]==1)return false;
		}
	}
	return true;
}

//만약 5,5주어지고 5장짜리면, 5 6 7 8 9 임 -> 10을 넘김녀 안됌, y도 마찬가지
bool check_size(int x, int y , int k) {
	if ((x + k >= 10) || (y + k >= 10)) return false;
	return true;
}

//k숫자만큼 1이 있는지 확인
bool check_paper(int x, int y, int k) {
	//3,3위치에서 k가 4이면 5장이라는거임 5장이면 3,4,5,6,7임 그러면 i는 3이고 i< 3+4+1인 8이어야함
	for (int i = x; i < x + k+1; i++) {
		for (int j = y; j < y + k+1; j++) {
			if (!map[i][j]) return false;
		}
	}
	return true;
}

void fill_paper(int x, int y, int k) {
	//k가 4이면 5장을 채워야한다는거임 x 가 3이면 3,4,5,6,7 이고 x+k가 3+4니까 7이다. 고로 8이 와야하므로 
	for (int i = x; i < x + k+1; i++) {
		for (int j = y; j < y + k+1; j++) {
			map[i][j] = 0;
		}
	}
}


void unfill_paper(int x, int y, int k) {
	//k가 4이면 5장을 채워야한다는거임 x 가 3이면 3,4,5,6,7 이고 x+k가 3+4니까 7이다. 고로 8이 와야하므로 
	for (int i = x; i < x + k + 1; i++) {
		for (int j = y; j < y + k + 1; j++) {
			map[i][j] = 1;
		}
	}
}
void solve(int cnt) {
	if (cnt > Answer) return;
	//색종이를 다 채운경우
	if (one_left()) {
		if (cnt < Answer) {
			Answer = cnt;
			return;
		}
	}

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j]==1) {
				for (int k = 4; k >= 0; k--) {
					if (paper[k] > 0 && check_size(i,j,k) && check_paper(i,j,k)) {
						paper[k]--;
						fill_paper(i, j, k);
						solve(cnt + 1);
						unfill_paper(i, j, k);
						paper[k]++;
					}
				}
				return;
			}
		}
	}
}

int main() {
	init();
	solve(0);
	if (Answer == 999999) { cout << "-1"; }
	else {
		cout << Answer;
	}
}