[JAVA] 17404 RGB거리 2

 

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

---

 

접근방법

1) 문제를 읽고 바로 dp라고 생각이 들었다 1행이 2행에 영향이 있고 ...  N행까지 영향을 주니까

2) 첫번째집을 R G B 각각 선택했을때 N행에서 만약 첫행 선택한 색이 R을 선택했다면 마지막행 R은 최솟값 선택에서 제외

3) 아래 그림을 그리면서 아이디어 획득함

이전 행에서 현재 색을 제외하고 최소값을 구해준다.

예를 들면 현재 레드2행 이라면 1행의 초록과 파랑중 더 작은값을 현재 레드행의 값과 합해준다.

위과정을 반복해주면서 마지막행에 도달한다

첫행에 선택한 수를 맥스값으로 바꿔줘 선택이 안되게 해준다.

import java.io.*;
import java.util.*;
public class Main {
	static int res=Integer.MAX_VALUE,N,comp[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		N = Integer.parseInt(br.readLine());
		comp = new int[N][3];
		for(int i=0;i<N;i++) {
			stz = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<3;j++) comp[i][j] = Integer.parseInt(stz.nextToken());
		}
		Exceptcolor(0);
		Exceptcolor(1);
		Exceptcolor(2);
		System.out.println(res);
	}
	private static void Exceptcolor(int idx) {
		int temp[][] = new int[N][3];
		for(int i=0;i<N;i++) temp[i] = Arrays.copyOf(comp[i], 3);
		temp[1][0] = temp[1][0] +temp[0][idx];
		temp[1][1] = temp[1][1] +temp[0][idx];
		temp[1][2] = temp[1][2] +temp[0][idx];
		temp[1][idx] = Integer.MAX_VALUE;
		
		for(int i=2;i<N;i++) {
			temp[i][0] = temp[i][0] + Math.min(temp[i-1][1], temp[i-1][2]);
			temp[i][1] = temp[i][1] + Math.min(temp[i-1][0], temp[i-1][2]);
			temp[i][2] = temp[i][2] + Math.min(temp[i-1][0], temp[i-1][1]);
		}
		temp[N-1][idx] = Integer.MAX_VALUE;
		
		int cnt=Integer.MAX_VALUE;
		for(int i=0;i<3;i++) {
			if(cnt>temp[N-1][i])cnt = temp[N-1][i];		
		}
		res = Math.min(cnt, res);
	}
}

 

느낀점

오랜만에 시간 1페이지를 뚫었다

이맛에 알고리즘 푸는것 같다.

dp는 감을 잡으면 굉장히 쉽고 아니면 어려운 부분이라 지속적으로 문제를 풀어줘야겠다고 생각함.