백준 1149번
https://www.acmicpc.net/problem/1149

문제

---

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

생각하기

---

• TopDown : 재귀
• Bottom Up : 반복문

동작

최속값을 찾아 누적합을 구하면 답을 구할 수 없음.
모든 경로의 경우의 수를 찾아서 작은 값들을 누적합으로 계산해서 찾아야 함

예를 들어
Red의 누적합을 구할경우, 이전의 집 색깔의 영향을 받기 때문에 Green과 Blue중에서만 선택이 가능하고, 이 중에서 작은 값을 선택하여 현재의 Red값과 합하면 조건에 맞는 누적합을 구할 수 있다.

코드

---

Java

Top-Down

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

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

public class Main {
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;

	static int arr[][];
	static int memo[][];
	static int N;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		memo = new int[N][3];
		arr = new int[N][3];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][Red] = Integer.parseInt(st.nextToken());
			arr[i][Green] = Integer.parseInt(st.nextToken());
			arr[i][Blue] = Integer.parseInt(st.nextToken());
		}

		memo[0][Red] = arr[0][Red];
		memo[0][Green] = arr[0][Green];
		memo[0][Blue] = arr[0][Blue];

		System.out.println( Math.min( DP(N-1, Red), Math.min(DP(N-1, Green), DP(N-1, Blue))   ));
	} // End of main

	private static int DP(int N, int color) {

		if(memo[N][color] == 0) {

			if(color == Red) {
				memo[N][Red] = Math.min( DP(N-1, Green), DP(N-1, Blue)) + arr[N][Red];
			}
			else if(color == Green) {
				memo[N][Green] = Math.min( DP(N-1, Red), DP(N-1, Blue)) + arr[N][Green];
			}
			else if(color == Blue) {
				memo[N][Blue] = Math.min( DP(N-1, Red), DP(N-1, Green)) + arr[N][Blue];
			}
		}

		return memo[N][color];
	} // End of DP
} // End of Main

Bottom-Up

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

public class Main {
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		int memo[][] = new int[N][3];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			memo[i][Red] = Integer.parseInt(st.nextToken());
			memo[i][Green] = Integer.parseInt(st.nextToken());
			memo[i][Blue] = Integer.parseInt(st.nextToken());
		}

		for(int i=1; i<N; i++) {
			memo[i][Red] += Math.min(memo[i-1][Green], memo[i-1][Blue]);
			memo[i][Green] += Math.min(memo[i-1][Red], memo[i-1][Blue]);
			memo[i][Blue] += Math.min(memo[i-1][Red], memo[i-1][Green]);
		}

		System.out.println(Math.min(memo[N-1][Red], Math.min(memo[N-1][Green], memo[N-1][Blue])));
	} // End of main
} // End of Main

Kotlin

Top-Down

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

private const val Red = 0; private const val Green = 1; private const val Blue = 2;
private lateinit var memo : Array<IntArray>
private lateinit var arr : Array<IntArray>
private var N = 0;

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    N = br.readLine().toInt()
    memo = Array(N, {IntArray(3)})
    arr = Array(N, {IntArray(3)})

    for(i in 0 until N) {
        var st = StringTokenizer(br.readLine())
        arr[i][Red] = st.nextToken().toInt()
        arr[i][Green] = st.nextToken().toInt()
        arr[i][Blue] = st.nextToken().toInt()
    }

    memo[0][Red] = arr[0][Red]
    memo[0][Green] = arr[0][Green]
    memo[0][Blue] = arr[0][Blue]

    print( Math.min(DP(N-1, Red), Math.min(DP(N-1, Green), DP(N-1, Blue))))
} // End of main

private fun DP(N : Int, color : Int) : Int {

    if(memo[N][color] == 0) {

        if(color == Red) {
            memo[N][Red] = Math.min( DP(N-1, Green), DP(N-1, Blue)) + arr[N][Red];
        }
        else if(color == Green) {
            memo[N][Green] = Math.min( DP(N-1, Red), DP(N-1, Blue)) + arr[N][Green];
        }
        else if(color == Blue) {
            memo[N][Blue] = Math.min( DP(N-1, Red), DP(N-1, Green)) + arr[N][Blue];
        }
    }

    return memo[N][color];
} // End of DP

Bottom-Up

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

private const val Red = 0; private const val Green = 1; private const val Blue = 2;
private lateinit var memo : Array<IntArray>
private lateinit var arr : Array<IntArray>
private var N = 0;

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    N = br.readLine().toInt()
    memo = Array(N, {IntArray(3)})
    arr = Array(N, {IntArray(3)})

    for(i in 0 until N) {
        var st = StringTokenizer(br.readLine())
        arr[i][Red] = st.nextToken().toInt()
        arr[i][Green] = st.nextToken().toInt()
        arr[i][Blue] = st.nextToken().toInt()
    }

    memo[0][Red] = arr[0][Red]
    memo[0][Green] = arr[0][Green]
    memo[0][Blue] = arr[0][Blue]

    print( Math.min(DP(N-1, Red), Math.min(DP(N-1, Green), DP(N-1, Blue))))
} // End of main

private fun DP(N : Int, color : Int) : Int {

    if(memo[N][color] == 0) {

        if(color == Red) {
            memo[N][Red] = Math.min( DP(N-1, Green), DP(N-1, Blue)) + arr[N][Red];
        }
        else if(color == Green) {
            memo[N][Green] = Math.min( DP(N-1, Red), DP(N-1, Blue)) + arr[N][Green];
        }
        else if(color == Blue) {
            memo[N][Blue] = Math.min( DP(N-1, Red), DP(N-1, Green)) + arr[N][Blue];
        }
    }

    return memo[N][color];
} // End of DP