[Baekjoon] 1149번 RGB거리 (Java)

예제 입력1

3
26 40 83
49 60 57
13 89 99

예제 출력1

96

 

 

예제 입력2

3
1 100 100
100 1 100
100 100 1

예제 출력2

3

 

 

예제 입력3

3
1 100 100
100 100 100
1 100 100

예제 출력3

102

 

 

예제 입력4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

 

예제 출력4

208

 

 

예제 입력5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력5

253

 

 

 

package Q1149;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		int[][] arr = new int[num][3];
		int[][] intArr = new int[num][3];
		for(int i = 0; i < arr.length; i++) {
			for(int j = 0; j < arr[i].length; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		
		for(int i = 0; i < arr.length; i++) {
			for(int j = 0; j < arr[i].length; j++) {
				if(i == 0) {
					intArr[i][j] = arr[i][j];
				}else {
					if(j == 0) {
						// [i-1][1]과 [i-1][2] 중 작은 값과 나를 더함
						intArr[i][j] = intArr[i-1][1] > intArr[i-1][2] ? arr[i][j]+intArr[i-1][2] : arr[i][j]+intArr[i-1][1];
					}else if(j == 1) {
						// [i-1][0]과 [i-1][2] 중 작은 값과 나를 더함
						intArr[i][j] = intArr[i-1][0] > intArr[i-1][2] ? arr[i][j]+intArr[i-1][2] : arr[i][j]+intArr[i-1][0]; 
					}else if(j == 2) {
						// [i-1][0]과 [i-1][1] 중 작은 값과 나를 더함
						intArr[i][j] = intArr[i-1][0] > intArr[i-1][1] ? arr[i][j]+intArr[i-1][1] : arr[i][j]+intArr[i-1][0]; 
					}
				}
			}			
		}
		int result = 0;
		for(int i = 0; i < 3; i++) {	// 해당 경우의 값을 저장한 마지막줄에서 가장 작은 값을 출력
			if(i == 0) {result = intArr[num-1][i]; }
			else if(result > intArr[num-1][i]){
				result = intArr[num-1][i];
			}
		}
		System.out.println(result);
	}
}

정수 삼각형 문제와 아주 유사한 문제

모든 갈 수 있는 경우의 수를 다 더해서 가장 작은 값을 출력