글 읽기 - 색종이 붙이기 반례좀 찾아주세요 ㅠㅠ

ekfrhkquf12 4년 전 0

코드를 간단하게 설명드리겠습니다.

1. 5개의 색종이에 대해서 사용할 색종이들을 먼저 DFS로 True False 조합을 만들어 mystack에 넣습니다.

2. mystack이 쌓이게 되면 calculate 함수로 넘어갑니다.

3. k=5부터 1까지 줄여 나가면서 가장 큰 색종이들부터 채워 나갑니다.

이 때 mystack에서 True인 색종이들만 사용합니다.

(check함수 사용)

4. 모든 색종이들이 다 덮였을 시에는 paper_count를 update합니다.

이런 식으로 코드를 작성하였습니다.

예제와, 질문 게시판의 반례들은 거진 통과하는 것 같습니다.

어떤 부분에서 잘못된 것인지 알려주시거나 반례를 찾아주시면 감사하겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
#include<queue>

using namespace std;
int papers[5];
int** matrix;
bool** visited;
int n = 10;
int paper_size = 0;
int paper_count = 101;
vector<bool> mystack;

void check(int p, int q);
void calculate();
void dfs();


int main() {
	for (int i = 0; i < 5; i++)
		papers[i] = 5;

	matrix = (int**)malloc(sizeof(int*)*n);
	visited = (bool**)malloc(sizeof(bool*)*n);
	for (int i = 0; i < n; i++) {
		matrix[i] = (int*)malloc(sizeof(int*)*n);
		visited[i] = (bool*)malloc(sizeof(bool*)*n);
		for (int j = 0; j < 10; j++) {
			//scanf("%d", &matrix[i][j]);
			cin >> matrix[i][j];
			visited[i][j] = false;
		}
	}

	
	dfs();
	if (paper_count == 101)
		printf("%d", -1);
	else printf("%d", paper_count);

}

void check(int p, int q) {
	//size만큼 들어갈 수 있는지를 확인해야 한다.
	//paper_size를 확인해서
	//mystack을 확인해서..!

	bool flag = true;
	for (int i = p; i < p + paper_size; i++) {
		for (int j = q; j < q + paper_size; j++) {
			if (i >= n || j >= n) {
				flag = false;
			}
			if (flag == false)
				break;

			if (visited[i][j]) {
				flag = false;
			}


			if (matrix[i][j] == 0) {
				flag = false;
			}

			if (flag == false)
				break;
		}
		if (flag == false)
			break;
	}

	if (flag == true) {
		papers[paper_size - 1] --;
		for (int i = p; i < p + paper_size; i++) {
			for (int j = q; j < q + paper_size; j++) {
				visited[i][j] = true;
			}
		}
	}	
}


void dfs() {
	if (mystack.size() == 5) {
		calculate();
	}

	else {
		for (int i = 0; i < 2; i++) {
			mystack.push_back(i); 
			dfs();
			mystack.pop_back();
		}

	}
};
	
void calculate() {
	for (int k = 5; k >= 1; k--) {
		if (mystack.at(k - 1) == true) {
			paper_size = k;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					if (!visited[i][j] && matrix[i][j] == 1) {
						check(i, j);
					}
				}
		}
	}

	bool flag = false;
	bool flag2 = false;
	
	for (int i = 0; i < 5; i++)
		if (papers[i] < 0) flag = true;


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && matrix[i][j] == 1) {
				flag2 = true;
			}
		}
		if (flag2 == true) break;
	}

	int count = 0;
	if (!flag && !flag2) {
		for (int i = 0; i < 5; i++) {
			count += 5 - papers[i];
		}

		if (paper_count >= count)
			paper_count = count;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visited[i][j] = false;

	for (int i = 0; i < 5; i++)
		papers[i] = 5;
}

baries 4년 전 5

1 1 1 1 1 1 1 0 0 0

1 1 1 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

minjoonist 3년 전 0

@baries 혹시 위 예제 올바른 답이 뭔가요?

baries 3년 전 1

@minjoonist 5 나오네요

minjoonist 3년 전 0

감사합니다 ㅎㅎ 근데 이미 문제를 풀긴 했는데 그래도 나중에 볼 사람들에게 도움되겠네요 ㅎㅎ

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

문제

문제

출처

ICPC

색종이 붙이기 반례좀 찾아주세요 ㅠㅠ

ekfrhkquf12 4년 전 0

baries 4년 전 5

minjoonist 3년 전 0

baries 3년 전 1

minjoonist 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말