글 읽기 - Testcase , 다른 Sample case도 올바르게 나오는데..질문드려요

mojunseo49 6년 전 0

제출하여보았지만 틀렸다고 나와서 질문드립니다.

제가 머리가 나빠서 획기적인 알고리즘은 구현하지못하였고..

제 방법은 이렇습니다.

전제는 첫번째 입력된 집의 비용이 아닌, 전체에서 가장 적은 비용이 드는 집부터 골라 색칠합니다.

testcase를 예로 들면 26이 아닌, 13부터 찾게 됩니다.(문제 이해를 잘못한건가요?)

일단 배열에 입력된 비용들을 저장합니다.

첫번째로 전체에서 가장 적은 비용인 13을 찾아 내었고, 그 집은 13이 해당된 RED로 색칠하였기 때문에

더이상 행 정보는 필요하지 않습니다. 또, 이웃집은 RED로 칠할 수 없기 때문에 13이 저장된 열의 위 아래도 필요하지 않습니다.

따라서 배열의 해당위치는 0으로 바꿉니다.

두번째로 13 다음으로 작은 비용을 찾아내고, 위와 같은 방법으로 0으로 바꿉니다.

모든 집을 채우게되면 최소값을 리턴합니다.

아래는 Test case 결과입니다.

26 40 83

0 60 57

0 0 0

------------------------
0 0 0

0 60 57

0 0 0

-------------------
0 0 0

0 0 0

-------------------
96

/*
 * 49%
문제/
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 
또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 
집 i의 이웃은 집 i-1과 집 i+1이다. 
처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 
모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력/
첫째 줄에 집의 수 N이 주어진다. 
N은 1,000보다 작거나 같다. 
둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.
	
출력/
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

*/

import java.util.Scanner;

public class RGBcolor {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int house = sc.nextInt();
		
		int color[][] = new int[house][3];
		for(int i=0;i<house;i++)
		{
			for(int j=0;j<3;j++)
			{
				color[i][j] = sc.nextInt();
			}
		}
		int result=0;
		int temp=0;
		int tempa=0;
		int tempb=0;
		//전체 집 만큼 반복한다.
		for(int i=0;i<house;i++)
		{

			//집에 채울 색을 찾기 위한 만큼 반복한다.
			for(int a=0;a<house;a++)
			{
				for(int b=0;b<3;b++)
				{
					//0이 아닌 값중에서 가장 작은 수를 찾는다. 찾는다면 옮기고, 그행과 값+1,-1을 0으롬 만든다.
					//만약 더 했을때 인덱스를 넘어가면 무시한다.
					if(temp == 0 && color[a][b]!=0)
					{
						temp = color[a][b];
						//System.out.println("temp set:"+temp);
					}

					if(temp >= color[a][b] && color[a][b] != 0)
					{
						temp = color[a][b];
						tempa = a;
						tempb = b;
						System.out.println(temp+"/"+a+"/"+b);
					}
				}
			}
			result += temp;
			temp = 0;
			
			
			if(tempa == 0)
			{
				if(tempb == 0)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa][tempb+2] = 0;
					color[tempa+1][tempb] = 0;
				}
				if(tempb == 1)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa+1][tempb] = 0;
				}
				if(tempb == 2)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb-2] = 0;
					color[tempa+1][tempb] = 0;
				}
			}
			if(tempa == (house-1))
			{
				if(tempb == 0)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa][tempb+2] = 0;
					color[tempa-1][tempb] = 0;
				}
				if(tempb == 1)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa-1][tempb] = 0;
				}
				if(tempb == 2)
				{
					color[tempa][tempb] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb-2] = 0;
					color[tempa-1][tempb] = 0;
				}
			}
			if(tempa != 0 && tempa != (house-1))
			{
				if(tempb == 0)
				{
					color[tempa-1][tempb] = 0;
					color[tempa+1][tempb] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa][tempb+2] = 0;
					color[tempa][tempb] = 0;
				}
				if(tempb == 1)
				{
					color[tempa-1][tempb] = 0;
					color[tempa+1][tempb] = 0;
					color[tempa][tempb+1] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb] = 0;
				}
				if(tempb == 2)
				{
					color[tempa-1][tempb] = 0;
					color[tempa+1][tempb] = 0;
					color[tempa][tempb-1] = 0;
					color[tempa][tempb-2] = 0;
					color[tempa][tempb] = 0;
				}
			}
			
			for(int q=0;q<house;q++)
			{
				for(int w=0;w<3;w++)
				{
					System.out.print(color[q][w]+" ");
				}
				System.out.printf("\n");
			}
		}
		System.out.println(result);
	}

}

gatlingfever 6년 전 1

알고리즘 자체가 최소값을 구할 수 없다고 생각됩니다.

문제의 해답인 최소비용을 구하기 위해서는 최소 비용 뿐만 아니라, 그걸 선택함에 따른 감가상각도 고려를 해야합니다.

(이때문에 저도 다른 알고리즘을 짜봤지만 답이 틀리더군요...)

간단한 예제를 들어드리겠습니다.

1 2 3

4 100 200

5 6 7

위의 경우, 눈으로 대충 봐도 답이 2, 4, 6순으로 선택해서 12임을 알수 있습니다.

하지만 님의 알고리즘 대로라면

1선택

0 0 0

0 100 200

5 6 7

5선택

0 0 0

0 100 200

0 0 0

100선택

0 0 0

답 : 106이 나오게 됩니다.

allkanet72 6년 전 1

전체 중에 최솟값을 먼저 칠하는 알고리즘은 그럴듯해 보이지만, 결과적으로는 최솟값이 안 나올 수 있습니다.
최솟값, 혹은 최댓값만 선택하는 것을 '탐욕적 알고리즘' 이라하는데 유의해서 사용해야합니다.
구글링을 하시면 많은 반례사례등을 얻으실 수 있습니다.

윗분의 사례처럼
1 2 3
4 100 200
5 6 7

탐욕적으로 푼다면 무조건 1이 선택되죠. 1-100-5 결과적으로는 최악의 선택이 되는 겁니다.

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%...

위키백과에도 정확히 정의 되어있습니다.

"최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다." 라구요

mojunseo49 6년 전 0

저도 글을 쓰고나서 케이스를 여럿 만들어해봤는데, 고정적인 케이스에서만 최솟값이 나오더군요.

점화식 공부를하고 식을 세워서 더 풀어봐야할 것같아요!

댓글 감사합니다!

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

문제

문제

출처

ICPC

Testcase , 다른 Sample case도 올바르게 나오는데..질문드려요

mojunseo49 6년 전 0

gatlingfever 6년 전 1

allkanet72 6년 전 1

mojunseo49 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말