백준 1149번 - RGB거리

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

1149번: RGB거리

 

이 문제는 각 층마다의 최솟값을 구하여 더하는 게 아니라 모든 경로의 경우의 수를 구하여 그 값 중 최솟값을 찾아야한다.

 

결과적으로 마지막에 RGB 중 R을 선택하는 경우, G를 선택하는 경우, B를 선택하는 경우 중 가장 최솟값을 찾아야한다.

 

 

https://st-lab.tistory.com/128 다음 블로그를 참고하여 쉽게 이해할 수 있었다.

[백준] 1149번 : RGB거리 - JAVA[자바]

 

 

코드

import java.io.*;
import java.util.*;

public class Main{
	static int rgb[][];
	static int price[][];
	
	static int fibo(int n, int index) 
	{
		if(price[n][index]==0)
		{
			if(index==0)
			{
				price[n][index] = Math.min(fibo(n-1,1),fibo(n-1,2)) + rgb[n][index];
			}
			else if(index==1)
			{
				price[n][index] = Math.min(fibo(n-1,0),fibo(n-1,2))+ rgb[n][index];
			}
			else {
				price[n][index] = Math.min(fibo(n-1,0),fibo(n-1,1))+ rgb[n][index];
			}
		}
		return price[n][index];
	}
	
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
	    rgb = new int[N][3];
	    price = new int[N][3];
	    
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<3;j++)
			{
				rgb[i][j] = sc.nextInt();
			}
		}
		price[0][0]=rgb[0][0];
		price[0][1]=rgb[0][1];
		price[0][2]=rgb[0][2];
		
		System.out.println(Math.min(fibo(N-1,2),Math.min(fibo(N-1,0),fibo(N-1,1))));
		
	}
}