BOJ_S1_1149

📁 [S1_1149] RGB거리

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

public class Main {
 	static StringTokenizer st;
	static int[][] arr;
	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());

		// 입력 값 저장 배열
		arr = new int[N][3];
		// 더한 값을 저장할 배열
		dp = new int[N][3];

		// 배열에 값 입력 ( 집 색깔 )
		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());
			}
		}
		
        // 초깃값 설정
		dp[0][0] = arr[0][0];
		dp[0][1] = arr[0][1];
		dp[0][2] = arr[0][2];

        // 색 별로 각각의 최종값
		long first = go(N - 1, 0);
		long second = go(N - 1, 1);
		long third = go(N - 1, 2);

        // 최솟값 구하기
		long res = Math.min(first, Math.min(second, third));

		System.out.println(res);

	}

    // dp 배열에 넣는 과정
	static int go(int i, int j) {

        // dp에 값이 없는 경우 if문안에 들어가고 dp에 값이 있는 경우 바로 가져온다 ( 메모이제이션 )
		if (dp[i][j] == 0) {
			if (j == 0) {
				dp[i][j] = arr[i][j] + Math.min(go(i - 1, j + 1), go(i - 1, j + 2));
			} else if (j == 1) {
				dp[i][j] = arr[i][j] + Math.min(go(i - 1, j - 1), go(i - 1, j + 1));
			} else {
				dp[i][j] = arr[i][j] + Math.min(go(i - 1, j - 1), go(i - 1, j - 2));
			}
		}

		return dp[i][j];
	}
}

🤔 나의 생각

그림을 그려서 보니 하향식 접근을 해야해서 DP문제라고 생각했다.
그래서 처음 값을 dp에 넣어주고 go 메서드를 통해 본인 열에 있는 값을 제외한 나머지 두 dp 값 중에 작은 것을 가져와 본인 값이랑 더해 dp 값을 구해주었다. ( go 메서드 설명 )
만약 dp 배열에 값이 있으면 바로 dp 값을 반환해주고 없으면 위에 말한 과정을 반복해주었다.