[Mindev 개발공부]알고리즘 백준 1149번 RGB거리 Java 풀이

문제는 다음과 같습니다.

접근방법

문제 예제를 보고 2차원 배열로 접근하였습니다.

여기서 힌트를 언게 되었습니다.

일단 첫번째줄은 가장 처음시작이니 3개의 숫자중 가장 작은수로 접근하면됩니다.

두번째줄부터는 각각 각각 숫자로 접근했을때 전의 값들을 유추 해보게 되었습니다.

예를들어 두번째줄의 60의 수에 접근하게될때 

전의 값을 유추 해볼때에는 첫번째 26 과 83 둘중 작은값이 되겠습니다.

이런 방법으로 2차원 배열을 봤을때

for (int i = 1; i < n; i++) {

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + list[i][0];

dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + list[i][1];

dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][2];

}

이러한 식을 얻을수있습니다.

전체 코드

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[][] list = new int[n][3];

int[][] dp = new int[n][3];

int sum = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < 3; j++) {

list[i][j] = sc.nextInt();

}

}

dp[0][0] = list[0][0]; 

dp[0][1] = list[0][1];

dp[0][2] = list[0][2];

for (int i = 1; i < n; i++) {

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + list[i][0];

dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + list[i][1];

dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][2];

}

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

}

}