글 읽기 - rgb 거리 문제 질문

joon8409 8년 전 0

dp 문제로 점화식을 사용하여 대충 i 번째에는 i-2까지의 결과를 사용해서 풀게 했는데 틀렸습니다가 나오네요

어디서 틀렸는지 잘 모르겠는데 어디서 틀렸을까요..?

#include<iostream>
#include<math.h>
int min(int a, int b)
{
	if (a > b)
	{
		return b;
	}
	else {
		return a;
	}
}
using namespace std;
static int credit[1002];
int main(void)
{
	int color[1002][3];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> color[i][j];
		}
		if (i == 0)
		{
			credit[i] = min(color[0][0], min(color[0][1], color[0][2]));
		}
		else if (i == 1)
		{
			credit[i] = min(color[0][0]+ color[1][1], 
						min(color[0][0]+ color[1][2], 
						min(color[0][1]+ color[1][0],
						min(color[0][1]+ color[1][2],
						min(color[0][2]+ color[1][0],
							color[0][2]+ color[1][1])))));
		}
		else {
			credit[i] =credit[i-2]+ min(color[i-1][0] + color[i][1],
									min(color[i - 1][0] + color[i][2],
									min(color[i - 1][1] + color[i][0],
									min(color[i - 1][1] + color[i][2],
									min(color[i - 1][2] + color[i][0],
										color[i - 1][2] + color[i][1])))));
		}
	}
	cout << credit[n - 1];
}

movie_jo 8년 전 0

else에서 i - 2에서 color[i-2][0]를 칠해도 i - 1에서 color[i - 1][0]을 칠해서 이웃끼리 같은 색을 칠하는 경우가 나올 수 있게 됩니다.

또 현재처럼 구현하실 경우 credit[i]가 i번째에서 색칠하는 비용의 최소값이 되는데,

이 경우 credit[0]에서 색깔이 고정되어 올바른 답이 나올 수 없게 됩니다.

joon8409 8년 전 0

오 감사합니다 생각해보니 2차원 배열로 이전에 쓴 색깔을 저장해야할거같군요

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

문제

문제

출처

ICPC

rgb 거리 문제 질문

joon8409 8년 전 0

movie_jo 8년 전 0

joon8409 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말