[백준]1149번 RGB거리(java)

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

1149번: RGB거리

백준 1149번 RGB거리 문제 링크입니다.

핵심

문제를 요약해보면, N개의 집이 있고, 인접한 집은 같은 색을 칠하지 못한다. 각 집마다 빨강, 초록, 파랑의 비용을 준다.

DP를 사용하는데, 최소 비용만을 구하는 것이 목적이다.

정답 코드

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

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][3];
        for (int i=0; i <n; i++){
            //arr[i][0] = 빨강/arr[i][1] = 초록/arr[i][2] = 파랑
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = 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]));
    }
}

해설

n을 입력 받는다. BufferferedReader가 Scanner에 비해 속도가 빠르므로 이번에는 BufferedReader를 사용하였다.

arr [i][0] 은 빨강을, arr [i][1] 은 초록을, arr [i][0] 은 파랑을 나타낸다.

최소비용을 구하는 과정을 통해 이전과 같은 색깔을 고르면 안 되고, 최소비용이 되는 값을 정한다.

n-1번째에 저장된 빨강 초록 파랑중 가장 작은 비용을 선택하면 된다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.