[Mindev 개발공부]알고리즘 백준 1932번 정수 삼각형 Java 풀이

문제는 다음과 같습니다.

접근방법

문제의 예제를 보고 2차원 배열로 생각해 보았습니다.

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

맨 좌측의 (5,1)까지 더한 값을 구하기 위해서는 (1,1)+(2,2)+(3,3)+(4,4)+(5,5) 하나의 방법 뿐입니다.

우측 (5,5)오 우측의 값들을 더하는 방법뿐입니다.

여기서 각 2차원배열의 값들을 반복문의 (i,j)로 바꾼다면 

좌측은 j가 1로 고정이며 우측은 i와j값이 같게 됩니다.

여기서 식을 유추할수 있습니다.

 

if (j == 1) {

list[i][j] = list[i - 1][j] + list[i][j];

} else if (i == j) {

list[i][j] = list[i - 1][j - 1] + list[i][j];

}

그럼 이제 좌측과 우측을 제외한 중앙의 값들을 보게되면 

(5,4)에 위치한 6이라는 값 까지 더하려면 (4,3) or (4,4) 둘중 더 큰 값과 합을 구해야합니다.

그러기 위해서는 다음과 같은 식이 필요합니다.

else {

list[i][j] = Math.max(list[i - 1][j], list[i - 1][j - 1]) + list[i][j]; -> 즉 (5,4)=(4,4) or (4,3) 중 큰값 + 현재 위치 값

}

전체 코드

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+1][n+1];

int sum = 0;

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

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

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

if (j == 1) {

list[i][j] = list[i - 1][j] + list[i][j];

} else if (i == j) {

list[i][j] = list[i - 1][j - 1] + list[i][j];

} else {

list[i][j] = Math.max(list[i - 1][j], list[i - 1][j - 1]) + list[i][j];

}

if (list[i][j] > sum)

sum = list[i][j];

}

}

System.out.println(sum);

}

}

문제 출처 https://www.acmicpc.net/problem/1932