[Java] 백준 1149번 RGB 거리

문제

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

1149번: RGB거리

알아야 할 개념

•  Dynamic Programming

풀이

나이브하게 모든 경우를 완전탐색한다고 하면, 경우의 수는 3^N 이다. 

점화식을 사용해 최적화를 한다.

구하고 싶은 단계가 k 라면, k-1 번째에 빨강, 파랑, 초록 으로 칠했을 때 최솟값을 안다면 k번째에 최솟값을 쉽게 구할수 있다. 

 

풀이 알고리즘은 다음과 같다.

1. 주어진 입력을 2차원 배열 map 에 저장한다.
2. 1행부터 N-1 까지 현재 위치 i행 k열(map[i][k]) 에서 다음을 수행한다.
   1. (i-1) 행 k열에서 (k+1)%3, (k+2)%3 의 최솟값을 현재 위치 에 더한다.
3. N-1 행의 최솟값을 비교해 리턴한다.

모듈러 연산을 이용해 다음 열의 위치를 탐색하였다.

 

코드

자바

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

public class Main {
   int map[][];
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        System.out.println(m.solution());
    }
    public int solution() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        map = new int[N][3];
        StringTokenizer st ;
        for(int i = 0; i< N ;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ;j < 3; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 1 ;i < N ; i++){
            for(int k = 0 ; k < 3;k++){
                map[i][k] += Math.min(map[i - 1][(k + 1) % 3], map[i - 1][(k + 2) % 3]);
            }
        }
        int ans = map[N-1][0];
        for(int i = 0 ;i < 3; i++){
            ans = Math.min(map[N-1][i], ans);
        }
        return ans;
    }
}