백준 1149: RGB거리(java/python)

문제

---

풀이

 

동적 프로그래밍을 이용해 풀이하는 문제다.

다른 DP 문제와 유사하나, N번 집의 색이 (N-1)번째 집의 색과 달라야 한다는 조건을 추가로 처리해 주어야 한다.

 

열의 원소가 0, 1, 2일 때를 각각 빨간색, 초록색, 파란색일 때라 하면

dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + arr[n][0] dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + arr[n][1] dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + arr[n][2]

와 같이 나타낼 수 있다. 

 

집의 개수와 집마다 각 색으로 칠하는 비용을 행과 열로 가진 2차원 배열 arr와 n번째 집까지의 비용 합을 저장할 2차원 배열 dp를 사용하였고, 이때 메모이제이션을 위해 dp는 Integer형으로 선언한다.

 

전체 코드

 

1. java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static Integer[][] dp;
	static int[][] arr;
	
	static int dp(int N, int c) {
		if(dp[N][c]==null) {
			if(c==0) {	//R
				dp[N][0]=Math.min(dp(N-1, 1), dp(N-1, 2))+arr[N][0];
			}
			else if(c==1) {	//G
				dp[N][1]=Math.min(dp(N-1, 0), dp(N-1, 2))+arr[N][1];
			}
			else {	//B
				dp[N][2]=Math.min(dp(N-1, 0), dp(N-1, 1))+arr[N][2];
			}
		}
		
		return dp[N][c];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());

		arr=new int[N][3];
		
		StringTokenizer st;
		
		for(int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			
			for(int j=0; j<3; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());	//R G B 0 1 2
			}
		}
		
		dp=new Integer[N][3];
		dp[0][0]=arr[0][0];
		dp[0][1]=arr[0][1];
		dp[0][2]=arr[0][2];
		
		int res=Math.min(Math.min(dp(N-1, 0), dp(N-1, 1)), dp(N-1, 2));
		System.out.println(res);
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());

		int[][] arr=new int[N][3];
		
		StringTokenizer st;
		
		for(int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			
			for(int j=0; j<3; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());	//R G B 0 1 2
			}
		}
		
		for(int i=1; i<N; i++) {
			arr[i][0]=Math.min(arr[i-1][1], arr[i-1][2])+arr[i][0];
			arr[i][1]=Math.min(arr[i-1][0], arr[i-1][2])+arr[i][1];
			arr[i][2]=Math.min(arr[i-1][0], arr[i-1][1])+arr[i][2];
		}
		
		int res=Math.min(Math.min(arr[N-1][0], arr[N-1][1]), arr[N-1][2]);
		System.out.println(res);
	}
}

굳이 배열을 2개씩이나 사용하지 않아도 될 것 같다.

물론 성능에는 크게 차이가 없다(위쪽 체크-배열 1개 사용, 아래쪽-2개 사용)

 

2. python

N=int(input())
arr=[[0]*3]*N

for i in range(N):
    arr[i]=list(map(int, input().split()))

for i in range(1, N):
    arr[i][0]=min(arr[i-1][1], arr[i-1][2])+arr[i][0]
    arr[i][1]=min(arr[i-1][0], arr[i-1][2])+arr[i][1]
    arr[i][2]=min(arr[i-1][0], arr[i-1][1])+arr[i][2]

print(min(arr[N-1][0], arr[N-1][1], arr[N-1][2]))