[백준] 1149번. RGB거리 (JAVA)

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

---

문제

---

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][n];

        StringTokenizer st;
        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());
            }
        }

        for(int i = 1; i < n; i ++){
            arr[i][0] += Math.min(arr[i-1][1], arr[i-1][2]);
            arr[i][1] += Math.min(arr[i-1][0], arr[i-1][2]);
            arr[i][2] += Math.min(arr[i-1][0], arr[i-1][1]);
        }

        System.out.println(Math.min(Math.min(arr[n-1][0], arr[n-1][1]), arr[n-1][2]));

    }
}

 

문제를 이해하면 코드를 작성하는 것은 간단하다.

 

첫 번째로, 단순하게 아래쪽을 바라보며 min을 진행하면 안 된다. 그 경우 100, 101, 102에서 100을 선택하더라도 만약 그다음 선택지가 1,  100, 100이었다면 손해를 볼 수 있기 때문이다. 따라서 위쪽을 바라보면서 코드를 진행하는 방향으로 설정했다.

 

내가 빨간색을 고른다면 윗쪽은 파란색 혹은 초록색을 골랐을 것이고, 이 중에서 더 작은 값을 선택하면 된다. 다만 여기서도 그 위쪽에 대한 고려가 되어있기 때문에 최솟값을 찾을 수 있다.