https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
이번 문제를 읽는데 무슨 내용인지 이해가 되지 않아 애를 먹었었다.
정리하자면 첫번째에서 RED 에서 골랐으면 두번째에선 RED를 제외한 BLUE OR GREEN 을 선택하고 세번째에선 나머지를 고르고, 이러한 경우 중 최소값을 고르면 되는 문제이다.
풀이는 아래와 같다.
# Process
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main
{
final static int Red = 0;
final static int Green = 1;
final static int Blue = 2;
static int[][] Cost;
static int[][] DP;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// RGB, 3가지의 경우이기 때문에 아래와 같이 선언
Cost = new int[N][3];
DP = new int[N][3];
StringTokenizer st;
for(int i = 0; i < N; i++)
{
st = new StringTokenizer(br.readLine(), " ");
Cost[i][Red] = Integer.parseInt(st.nextToken());
Cost[i][Green] = Integer.parseInt(st.nextToken());
Cost[i][Blue] = Integer.parseInt(st.nextToken());
}
// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
DP[0][Red] = Cost[0][Red];
DP[0][Green] = Cost[0][Green];
DP[0][Blue] = Cost[0][Blue];
// 3가지 최솟값 중에서도 최소를 구하면 된다.
System.out.println(Math.min(Paint_cost(N - 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
}
static int Paint_cost(int N, int color)
{
// 만약 탐색하지 않은 배열이라면
if(DP[N][color] == 0)
{
// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
if(color == Red)
{
DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
}
else if(color == Green)
{
DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
}
else
{
DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
}
}
return DP[N][color];
}
}
참고
https://st-lab.tistory.com/128