글 읽기 - 1149 번 질문입니다... 테스트 케이스도 많이 해봤는데 안되네요요

mts90 5년 전 0

마지막 번지의 숫자를 지정해서

아래로 쭉 내려가면서 최소값을 찾으려고 했는데요

아래 테스트 케이스는 다 잘 나오는데 뭐가 문제일까요???

1 10 100

100 5 50

100 20 100

=======================

2 1 3

2 1 5

5 4 3

=======================

1 2 3

4 5 6

9 8 7

========================

1 2 3

4 100 200

5 6 7

========================

1 2 3

4 100 200

5 6 7 12

=======================

#include <stdio.h>

int x[1000][3];
int money[1000][3];

int minsearch(int n)
{
	int min;
	min= x[n-1][0] > x[n-1][1] ? (x[n-1][1] > x[n-1][2] ? x[n-1][2]:x[n-1][1]) : (x[n-1][0] > x[n-1][2] ? x[n-1][2] : x[n-1][0]);

	return min;
}

int search(int n, int i)
{
	int min;

	if (i==0)
		min = money[n][1] > money[n][2] ? 2 : 1;
	else if (i==1)
		min = money[n][0] > money[n][2] ? 2 : 0;
	else if (i==2)
		min = money[n][0] > money[n][1] ? 1 : 0;

	return min;
}

int main ()
{
	int n,r,g,b;
	int min,i,j=0;
	int minimum;
	int sum=0;

	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d %d %d",&r,&g,&b);
		money[i][0]=r;
		money[i][1]=g;
		money[i][2]=b;
	}

	x[0][0]=money[0][0];
	x[0][1]=money[0][1];
	x[0][2]=money[0][2];

	if(n==2)
	{
		for (j=0;j<3;j++)
		{
			minimum=search(0,j);
			sum=money[0][minimum];
			x[1][j]=sum+money[1][j];
		}
	}

	if(n>2)
	{	
		for (j=0;j<3;j++)
		{
			sum=0;
			minimum=j;
			for (i=n-2;i>=0;i--)
			{
				minimum=search(i,minimum);
				sum+=money[i][minimum];
			}
			x[n-1][j]=sum+money[n-1][j];
		}

	}
	min=minsearch(n);
	printf("%d\n",min);

	return 0;

}

njw1204 5년 전 2

njw1204 5년 전 1

마지막 집부터 첫번째 집까지 돌면서

각 단계마다 칠할 수 있는 색 중에 가장 비용이 적은 색을 칠하게 짜셨는데..

이런 그리디한 방법으로는 풀리지 않습니다.

어떤 단계에서 손해보는 선택을 한 것이 전체적으로는 이득이 될 수도 있습니다.

mts90 5년 전 0

아... 그리디로는 안풀리는군여... 감사합니다

고수님의 지식에 감탄하고 갑니다!!!!

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

문제

문제

출처

ICPC

1149 번 질문입니다... 테스트 케이스도 많이 해봤는데 안되네요요

mts90 5년 전 0

njw1204 5년 전 2

njw1204 5년 전 1

mts90 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말