[ 백준 17136 ] 색종이 붙이기 (C++)

# 문제링크

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

로직은 잘 짠거같은데 "틀렸습니다"가 떴다. 다시 생각해보니, map 배열을 딱 map[10][10] 사이즈만큼 주고서는 r, c 범위를 제대로 지정해주지 않았다. r, c 따로 적는게 귀찮을 것 같아서 place 를 1~99 까지 하고, r = place / 10, c = place %10 으로 주었다. 그런데, 이렇게 두고 범위 검사를 해주지 않았다. 예를 들어, 종이 가장자리에서 2 사이즈의 종이를 붙이려고 시도하면, 범위 밖이니까 시도하면 안되는건데 그냥 되게 해두었다 ㅠㅠ

 

그래서 그냥 map을 map[15][15] 로 주었다. 그럼 입력받지 않은 부분은 어차피 0으로 초기화 될 테니, 검사를 해주지 않아도 색종이를 붙이지 못하게 된다.. ㅠㅠ 

 

쉽다고 생각했는데, 배열 범위가 복병이 되었다. 정말 PS는 방심할 수가 없다... ㅠㅠㅠ

 

# 제출 코드 

 

#include <cstdio>
using namespace std;

int map[15][15];
int total = 0;

void Input() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j]) total++;
		}
	}
}

int ans = 0;

bool Check(int place, int num) {
	int r = place / 10;
	int c = place % 10;
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			if (map[i][j] == 0)return false;
		}
	}
	return true;
}

void Attach(int place, int num, int paper) {
	int r = place / 10;
	int c = place % 10;
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			map[i][j] = paper;
		}
	}
}

int paper[] = { 0, 5, 5, 5, 5 ,5 };

void DFS(int place, int used, int cnt) {
	if (used >= ans) return;
	if (cnt == 0) {
		ans = used;
		return;
	}
	if (place >= 100) return;

	int r = place / 10;
	int c = place % 10;
	if (map[r][c] == 1) {
		for (int i = 5; i >= 1; i--) {
			if (paper[i] == 0)continue;
			if (Check(place, i)) {
				Attach(place, i, 0);
				paper[i]--;
				DFS(place + i, used + 1, cnt - i * i);
				paper[i]++;
				Attach(place, i, 1);
			}
		}
	}
	else {
		DFS(place + 1, used, cnt);
	}
}
int main() {
	//freopen("sample_input.txt", "r", stdin);
	Input();
	
	ans = 0x7ffffff;
	DFS(0, 0, total);
	printf("%d\n", (ans== 0x7ffffff)? -1 : ans);
}