글 읽기 - 예제로 있는건 모두 정상작동하는데, 틀렸다고 나옵니다..

bwnabi 6년 전 0

DP(DFS)를 이용해서 풀었고, 반례를 찾아서 해봐도 잘 안되네요..

왜 안 되는지 궁금합니다.

추가로 필요한 정보 있으시면 댓글로 남겨주세요

#if 1

#include <stdio.h>

#define MAX		(1000+100)
#define	NO		0
#define RED		1
#define GREEN	2
#define	BLUE	3
int N;

int a[MAX];
int R[MAX];
int G[MAX];
int B[MAX];
int min;

void input() {
	int i;
	scanf("%d", &N);

	// 초기화
	for (i = 0; i <= MAX; i++) {
		R[i] = 0; G[i] = 0; B[i] = 0;
	}
	min = 0xFFFFFF;
	for (i = 2; i <= N+1; i++) {
		scanf("%d %d %d", &R[i], &G[i], &B[i]);
	}

}

// 색칠할 건물번호, 왼쪽왼쪽 색상, 왼쪽 색상, 이번 시공을 하면 나오는 비용
void DFS(int i, int left_left_color, int left_color, int PRICE, int flag) {

	//printf("i : %d, %d, %d, %d, %d\n", i, left_left_color, left_color, PRICE, min);
	
	// 최적1
	if (min != 0xffffff && min < PRICE) return;
	//printf("%d_color : %d, %d\n", i+1, a[i-1],a[i]);
	// 종료조건
	if (i == N+1) {
		if (min > PRICE) min = PRICE;
		return;
	}

	// 마지막 예외
	if (i == N) {
		if (left_color == RED) {
			//printf("INIT 2\n");
			DFS(i + 1, left_color, GREEN, PRICE + G[i + 1], 1);
			DFS(i + 1, left_color, BLUE, PRICE + B[i + 1], 1);
		}
		else if (left_color == GREEN) {
			DFS(i + 1, left_color, RED, PRICE + R[i + 1], 1);
			DFS(i + 1, left_color, BLUE, PRICE + B[i + 1], 1);
		}
		else if (left_color == BLUE) {
			DFS(i + 1, left_color, RED, PRICE + R[i + 1], 1);
			DFS(i + 1, left_color, GREEN, PRICE + G[i + 1], 1);
		}

	}


	// step
	if (flag == 1) {
		if ((left_color == BLUE && left_left_color == GREEN) || (left_color == GREEN && left_left_color == BLUE)) {
			DFS(i + 1, left_color, RED, PRICE + R[i + 1], 1);
		}
		if ((left_color == RED && left_left_color == BLUE) || (left_color == BLUE && left_left_color == RED)) {
			DFS(i + 1, left_color, GREEN, PRICE + G[i + 1], 1);
		}
		if ((left_color == RED && left_left_color == GREEN) || (left_color == GREEN && left_left_color == RED)) {
			DFS(i + 1, left_color, BLUE, PRICE + B[i + 1], 1);
		}
	}
	// 초기 조건
	if (left_left_color == 0 && left_color == 0) {
		DFS(i + 1, 0, RED, PRICE + R[i + 1], 0);
		DFS(i + 1, 0, GREEN, PRICE + G[i + 1], 0);
		DFS(i + 1, 0, BLUE, PRICE + B[i + 1], 0);
	}	
	else if (left_left_color == 0 && left_color == RED) {
		DFS(i + 1, left_color, GREEN, PRICE + G[i + 1], 1);
		DFS(i + 1, left_color, BLUE, PRICE + B[i + 1], 1);
	}
	else if (left_left_color == 0 && left_color == GREEN) {
		DFS(i + 1, left_color, RED, PRICE + R[i + 1], 1);
		DFS(i + 1, left_color, BLUE, PRICE + B[i + 1], 1);
	}
	else if (left_left_color == 0 && left_color == BLUE) {
		DFS(i + 1, left_color, RED, PRICE + R[i + 1], 1);
		DFS(i + 1, left_color, GREEN, PRICE + G[i + 1], 1);
	}

	
}


int main() {

	input();
	DFS(1, 0, 0, 0, 0);
	printf("%d", min);

}

#endif

djm03178 6년 전 1

혹시나 하는 생각인데요, 비용의 범위가 주어지지 않았기 때문에 그 비용이 0xffffff보다 큰 경우를 고려해야 할 수도 있습니다. 0xffffff면 1677만 7215인데, int형의 한계치는 아직 멀었죠. 이 안에서는 값이 다 나올 수 있다고 보셔야 할 것 같습니다. limits.h의 INT_MAX 같은 걸 사용하시는 게 안전합니다.

bwnabi 6년 전 0

좋은 답변 감사합니다.
하지만 아쉽게도 INT_MAX를 사용해도 마찬가지로 틀렸다고 나오네요.. ㅠ

djm03178 6년 전 1

그러면 반례를 찾아드릴게요.

1 2 3

정답은 6인데, 7을 출력하네요.

bwnabi 6년 전 0

여기서부터가 문제인건가요..
왜 정답이 6인지를 모르겠네요..

1 2 3 1 이 되어야 양옆에 색상이 중복이 안되지않나요?
1 2 1 2 라면 가운데 있는 숫자 2의 이웃이 1로 같은 색상이 되니까요. 1도 마찬가지구요

djm03178 6년 전 1

문제의 서술이 약간 애매모호하기는 한데, 그런 뜻이 아닙니다.

"또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다."

이걸 잘 해석하셔야 됩니다. '이웃'은 같은 색으로 칠할 수 없습니다.

"집 i의 이웃은 집 i-1과 집 i+1이다."

그렇다면 집 i-1과 집 i+1이 i의 이웃이기 때문에 같은 색으로 칠할 수 없는 걸까요? 그렇지 않습니다. 여기서 같은 색으로 칠할 수 없는 건 서로 '이웃'인 것들끼리 뿐입니다.

따라서 위 예시에서 1 2 1 2 같은 선택이 가능합니다.

bwnabi 6년 전 0

... 언어의 문제였군요?
덕분에 해결했습니다....;
코드가 더 쉬워졌어요..

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

문제

문제

출처

ICPC

예제로 있는건 모두 정상작동하는데, 틀렸다고 나옵니다..

bwnabi 6년 전 0

djm03178 6년 전 1

bwnabi 6년 전 0

djm03178 6년 전 1

bwnabi 6년 전 0

djm03178 6년 전 1

bwnabi 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말