[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)1149번, RGB거리

문제 링크

1149번: RGB거리

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

아래 표는 예제 1,2,3에 최소값일 때를 표현한 것입니다.

R	G	B
26	40	83
49	60	57
13	89	99

R	G	B
1	100	100
100	1	100
100	100	1

R	G	B
1	100	100
100	100	100
1	100	100

규칙과 표에 선택된 것을 살펴보면 규칙이 보인다.

바로 그 이전에 선택되었던 색깔은 선택되지 않는다는 것입니다.

예를 들어 이전에 빨간색이 선택되었다면 다음 건물의 색깔은 초록색 아니면 파란색이 된다는 것입니다.

N의 최대값으로 건물의 개수를 기준과 RGB로 색깔이 3개이므로 [건물의 개수][3]으로 메모이제이션을 구성하였습니다.

배열 인덱스를 기준으로 색깔을 나누었습니다.

빨간색 : 0           초록색 : 1          파란색 : 2

이전 색깔과 동일하게 선택되지 않아야 하기 때문에 알고리즘은

 

이전 색깔이 빨간색일 때는 초록색과 파란색 중 선택했을 때를 비교하여 최소값을 얻는다.

이전 색깔이 초록색일 떄는 빨간색과 파란색 중 선택했을 때를 비교하여 최소값을 얻는다.

이전 색깔이 파란색일 때는 빨간색과 초록색 중 선택했을 때를 비교하여 최소값을 얻는다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• RGB를 칠하는 비용값을 저장하는 num을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 건물 색을 칠하는 최소 비용값을 얻는 함수 RGBstreet을 만들었습니다.

• check가 null이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• null인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 위에 알고리즘 설명을 토대로 RGBstreet 함수를 작성하였습니다.

결과 코드

//색깔 인덱스 표시 : 빨간색 = 0, 초록색 = 1, 파란색 = 2
import java.io.*;
import java.util.*;
public class Main{
	static long[][] check;		//메모이제이션 배열
	static int [][] num;		//비용 값 저장 배열
	static long min=Integer.MAX_VALUE;	//최소값
	static int index;	//건물의 개수
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //BufferedWriter를 통해 결과 값 출력
        //---------------배열 초기화 및 입력값 받기-----------
    	index = Integer.parseInt(br.readLine());
    	num = new int[index][3];
    	check = new long[index][3];
    	StringTokenizer st;
    	for(int i=0;i<index;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		num[i][0] = Integer.parseInt(st.nextToken());
    		num[i][1] = Integer.parseInt(st.nextToken());
    		num[i][2] = Integer.parseInt(st.nextToken());
    	}
        //-------------------함수 실행 및 최소값 구하기-----------------
    	min = Math.min(RGBstreet(0, 0),Math.min(RGBstreet(0, 1), RGBstreet(0, 2)));
    	bw.write(min + "\n");	//최소값 BufferedWriter에 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //-------------RGB건물 색칠 비용 구하는 함수----------------
	public static long RGBstreet(int n,int color) {
		if(n==index-1) 		//색칠 마지막 건물일 때
			return num[n][color];
		if(check[n][color]!=0)	//메모이제이션에 있는 값일 때
			return check[n][color];
		if(color==0)	//빨간색일때
			check[n][color] =  Math.min(RGBstreet(n+1, 1), RGBstreet(n+1, 2)) + num[n][color];
		else if(color==1)	//초록색일때
			check[n][color] =  Math.min(RGBstreet(n+1, 0), RGBstreet(n+1, 2)) + num[n][color];
		else		//파란색일때
			check[n][color] =  Math.min(RGBstreet(n+1, 0), RGBstreet(n+1, 1)) + num[n][color];
		return check[n][color];
		}
	}