글 읽기 - 반레를 못찾겠습니다...도와주십쇼

xogns09 4년 전 0

반정도에서 오답이 나오는데 아무리 찾아봐도 모르겠습니다. ㅠㅠ 정답 코드들과 비교해봐도 똑같은 과정인거같은데 뭘 놓치고 있는걸까요..

#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++) {
		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;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반레를 못찾겠습니다...도와주십쇼

xogns09 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말