글 읽기 - 왜 틀렸을까요?ㅠㅠ

ds04030 4년 전 0

색종이를 5x5부터 1x1 순서대로 가능한 곳을 찾아가면서 풀도록 하였습니다.

5x5를 최대한 놓고 1 => 0으로 바꾼다.

4x4를 ...

...

1x1 ...

위와 같은 알고리즘으로 풀었는데 왜 틀리는 걸까요? 혹시 제 알고리즘에 어떤 문제가 있는지 아시는분 도움 부탁드립니다. !!

/*
	색종이 붙이기
*/

#include <iostream>
using namespace std;

int map[10][10];
int num = 0;
int a = 5, b = 5, c = 5, d = 5, e = 5;
void solve();

int main()
{
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) num++;
		}
	}
	solve();
	if (num == 0) cout << 25 - a - b - c - d - e << "\n";
	else cout << "-1\n";
	return 0;
}

void solve() {
	for (int sz = 5; sz >= 1; sz--) {
		for (int i = 0; i <= 10 - sz; i++) {
			for (int j = 0; j <= 10 - sz; j++) {
				bool check = true;
				
				for (int k = i; k < i + sz; k++) {
					for (int r = j; r < j + sz; r++) {
						if (map[k][r] == 0) {
							check = false;
							break;
						}
					}
					if (!check) break;
				}

				if (check) {
					for (int k = i; k < i + sz; k++) {
						for (int r = j; r < j + sz; r++) {
							map[k][r] = 0;
						}
					}
					switch (sz) {
					case 1:
						if (a > 0) {
							a--;
							num -= 1;
						}
						break;
					case 2:
						if (b > 0) {
							b--;
							num -= 4;
						}
						break;
					case 3:
						if (c > 0) {
							c--;
							num -= 9;
						}
						break;
					case 4:
						if (d > 0) {
							d--;
							num -= 16;
						}
						break;
					case 5:
						if (a > 0) {
							e--;
							num -= 25;
						}
						break;
					}
				}
			}
		}
	}
}

chw0501 4년 전 1

위의 풀이는 그리디 알고리즘으로 푼것 같습니다.

하지만 꼭 5*5를 최대한 많이 쓴다고해서 전체 사용하는 개수가 줄어드는 것은 아닙니다.

예를 들어

1 1 1 1 1

1 1 1 1 0

위의 경우는 7개의 색종이로 붙일 수 있지만

4*4를 먼저 사용하면 불가능(-1)를 출력하게 됩니다.

백트래킹으로 5*5 붙여보고 다시 되돌리고 4*4붙여보고 다시 되돌리는 dfs방법으로 해결하는게 직관적인 풀이방법입니다.

ds04030 4년 전 0

감사합니다 결국 이문제는 못풀겠어서 다른 분들 코드를 참고했네용 ㅜㅜ

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

문제

문제

출처

ICPC

왜 틀렸을까요?ㅠㅠ

ds04030 4년 전 0

chw0501 4년 전 1

ds04030 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말