글 읽기 - 2590 문제 질문입니다.

chatterboy 9년 전 0

안녕하세요.

현재 가지고 있는 가장 큰 색종이를 좌측 상단부터 시작해서 놓는 방법으로

구현을 했습니다. 그리디하게 접근을 했는데 잘못 접근을 한 것일까요?

#include<cstdio>

#define N 6

int noBlocks[N + 1], bd[N + 1][N + 1];

void place_block(int y, int x, int size) {
    int i, j;
	for (i = y; i <= y + size - 1; i++)
		for (j = x; j <= x + size - 1; j++)
			bd[i][j] = 1;
}
int is_possible_to_place(int y, int x, int size) {
	int i, j, ret;
	ret = 1;
	for (i = y; i <= y + size - 1; i++)
		for (j = x; j <= x + size - 1; j++)
			ret &= bd[i][j] == 0;
	return ret;
}
void use_blocks() {
	int i, j, s;

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			bd[i][j] = 0;

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			for (s = 6; s >= 1 ; s--)
				if (is_possible_to_place(i, j, s) && noBlocks[s] >= 1) {
					noBlocks[s]--;
					place_block(i, j, s);
					break;
				}
}
int is_all_used() {
	int i, ret;
	ret = 1;
	for (i = 1; i <= N; i++)
		ret &= noBlocks[i] == 0;
	return ret;
}
int main() {
	int i, ans;
//	FILE *fin, *fout;

//	fin = fopen("input.txt", "r");
//	for (i = 1; i <= N; i++) fscanf(fin, "%d", &noBlocks[i]);
//	fclose(fin);
	for (i=1; i<=N; i++) scanf("%d", &noBlocks[i]);

	ans = 0;
	while (!is_all_used()) {
		use_blocks();
		ans += 1;
	}

//	fout = fopen("output.txt", "w");
//	fprintf(fout, "%d", ans);
//	fclose(fout);
	printf("%d", ans);
}

movie_jo 9년 전 1

혹시 is_possible_to_place()에서 배열범위 체크를 안해줘서 틀린 것 아닐까요

chatterboy 9년 전 0

@movie_jo

해봐야겠네요 ㅎㅎ

실마리 제공 감사합니다 ! :O

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

문제

문제

출처

ICPC

2590 문제 질문입니다.

chatterboy 9년 전 0

movie_jo 9년 전 1

chatterboy 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말