글 읽기 - RGB 거리 왜 틀렸는지 모르겠어요...

hotgkswjddn 9년 전 0

제 생각에는 맞게 짠 거 같은데 계속 틀렸다고 하네요...

지적해주시면 감사하겠습니다...

#include <stdio.h>

int arr[1010][3];
int res[1010][3];

int idx[3] = {0, 1, 2};	//1번의 이전, 2번의 이전, 3번의 이전 타일 상태 저장

int main(void)
{
	int N;
	int i, j;
	
	int max=0;

	scanf("%d", &N);

	for(i=0; i<N; i++)	{
		scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
	}

	for(i=0; i<3; i++)	{
		res[0][i] = arr[0][i];
	}

	for(i=1; i<N; i++)	{
			for(j=0; j<3; j++)	{
				if(idx[j] == 0)	{
					res[i][j] = res[i-1][j] + (arr[i][1] < arr[i][2] ? arr[i][1] : arr[i][2]);
					idx[j] = (arr[i][1] < arr[i][2] ? 1 :2);
				}
				else if(idx[j] == 1)	{
					res[i][j] = res[i-1][j] + (arr[i][0] < arr[i][2] ? arr[i][0] : arr[i][2]);
					idx[j] = (arr[i][0] < arr[i][2] ? 0 :2);
				}
				else if(idx[j] == 2)	{
					res[i][j] = res[i-1][j] + (arr[i][0] < arr[i][1] ? arr[i][0] : arr[i][1]);
					idx[j] = (arr[i][0] < arr[i][1] ? 0 :1);
				}

			}	//j
	}	//i

	max = res[i-1][0] < res[i-1][1] ? res[i-1][0] : res[i-1][1];
	max = max < res[i-1][2] ? max : res[i-1][2];

	printf("%d\n", max);

	return 0;
}

zzapCoder 9년 전 0

다음과 같은 테스트케이스에 대해 생각해보세요.

집이 3개 있고 첫번째 집의 RGB 색칠 비용은 1000 999 999,

두번째 집의 RGB색칠 비용이 999 1000 1000,

세번째 집의 RGB색칠 비용이 1 1001 1001 이라고 하면,

여기서 색칠할수 있는 최적 값은 GBR이나 BGR을 골라서 2000입니다. (999 -> 1000 -> 1)

그런데 지금 코드로는 2001만 답으로 나오는군요.

동적계획법에 관해 알아보시면 좋을 것 같습니다. :)

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB...

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

문제

문제

출처

ICPC

RGB 거리 왜 틀렸는지 모르겠어요...

hotgkswjddn 9년 전 0

zzapCoder 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말