[백준] 1149 RGB거리 - JAVA

1. 문제 유형 : DP

2. 시간복잡도 : O(3N)

 

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

public class Main {

	public static int N, cache[][], price[][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		cache = new int[N][3];
		price = new int[N][3];
	
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < 3; j++) {
				price[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = Integer.MAX_VALUE;
		for (int i = 0; i < 3; i++) {
			answer = Math.min(solve(0, i), answer);
		}
		System.out.println(answer);
		
	}
	
	public static int solve(int house, int color) {
		if(house == N-1) return price[house][color];
		
		if(cache[house][color] != 0) return cache[house][color];
		
		// R : 0, G : 1, B : 2
		if(color == 0) cache[house][color] = Math.min(solve(house+1,  1), solve(house+1, 2)); 
		if(color == 1) cache[house][color] = Math.min(solve(house+1,  0), solve(house+1, 2)); 
		if(color == 2) cache[house][color] = Math.min(solvN(e(house+1,  0), solve(house+1, 1));
		return cache[house][color] += price[house][color];
	}

}

 

참고

예전에 C++로 풀이했던 내용이다. 위 자바 코드는 하향식, 아래 c++코드는 상향식 코드이다.

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int cache[3];;
int color[1000][3];

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    }
    // 첫 번째
    memcpy(cache, color[0], sizeof(cache));
    
    for(int i=1; i<n; i++){
        int temp[3];
        temp[0] = min(cache[1]+color[i][0], cache[2]+color[i][0]); // R
        temp[1] = min(cache[0]+color[i][1], cache[2]+color[i][1]); // G
        temp[2] = min(cache[0]+color[i][2], cache[1]+color[i][2]); // B
        memcpy(cache, temp, sizeof(cache));
    }
    int mini = 987654321;
    for(int i=0; i<3; i++){
        mini = min(mini, cache[i]);
    }
    cout << mini << endl;
    return 0;
}