[Java] (배열) 정수 삼각형에서 최대값 루트 구하기 (동적계획법)

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangleresult

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

30

 

public class study230407_01 {

    public static int solution(int[][] triangle) {
        int answer = 0;
       
    	System.out.println("triangle.length : "+triangle.length);
    	int [][] result = new int[triangle.length][triangle.length];
    	result[0][0] = triangle[0][0];
    	result[1][0] = triangle[0][0] + triangle[1][0]; 
    	result[1][1] = triangle[0][0] + triangle[1][1];
    	
    	// 모서리 배열 구하기
    	for(int i=2; i<triangle.length; i++) {
    		result[i][0] = result[i-1][0] + triangle[i][0];
    		result[i][i] = result[i-1][i-1] + triangle[i][i];
    	}
    	
    	// 안쪽 배열 구하기
    	for(int i=2; i<triangle.length; i++) {
    		System.out.println(i);
    		for(int j=1; j<=i-1; j++) { // [i][0], [i][i]는 구해놨기 때문에 안쪽을 구한다
    			result[i][j] = max(result[i-1][j-1],result[i-1][j])+triangle[i][j];
    			System.out.println("result["+i+"]["+j+"] = "+result[i][j]);
    		}
    	}
    	
    	for(int i=0; i<result.length; i++) {
    		System.out.println("result["+i+"] : "+Arrays.toString(result[i]));
    	}
    	
    	
        answer = -1;
        for(int k=0; k<triangle.length; k++){
            if(result[triangle.length-1][k] > answer)
                answer = result[triangle.length-1][k] ;
        }
        
        return answer;
    }
    
    public static int max (int num1, int num2) {
    	int result = 0;
    	if(num1>num2) {
    		result = num1;
    	}else {
    		result = num2;
    	}
    	return result;
    }
    
    public static void main(String[] args) {
    	
    	int [][] triangle = {
    			{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}
    	};
    	System.out.println(solution(triangle));
	}
    
}

 

<해설>

 

문제 자체는 복잡하지 않다. 본인은 처음 읽었을 때 경우의 수를 다 구해서 그 중 최대값을 비교하라는 얘기인 줄 알고 그 경우의 수에 대한 배열을 구하려고 했으나 이게 만만치 않은 일임을 깨닫고 그냥 다른 분의 해설을 보기로 했다...^^

 

그림을 보면 알겠지만 1행과 2행은 고정이다. 여기서 1행의 1열까지의 합계를 result[0][0], 2행의 1열까지의 합계를 result[1][0]이라고 선언한다. 

 

 

1~2행까지는 바로 구할 수 있다.

result[0][0] = triangle[0][0];
result[1][0] = triangle[0][0] + triangle[1][0]; 
result[1][1] = triangle[0][0] + triangle[1][1];

 

양 사이드도 쉽게 구할 수 있다.

// 모서리 배열 구하기
for(int i=2; i<triangle.length; i++) {
    result[i][0] = result[i-1][0] + triangle[i][0];
    result[i][i] = result[i-1][i-1] + triangle[i][i];
}

 

문제는 안쪽인데, 경우의 수를 다 구해야 하느냐? 아니다. 쉽게 생각해보자. 결국 문제의 목적은 최대값만 구하면 되는 것이다. 3행의 2열부터 보자. 여기서 행을 i로, 열을 j라고 하자. triangle[i][j]의 값이 1일 때, result[i][j]는 result[i-1][j-1]과 result[i-1][j] 중 더 큰 값과 해당 위치에 있는 triangle[i][j] 값을 더한 것이다. 여기서 숫자를 비교할 땐 그냥 쌩 조건문으로 써도되고 max라는 스태틱 함수를 따로 선언해서 써도된다. 본인은 함수를 따로 만들어 썼다.

 

// 안쪽 배열 구하기
for(int i=2; i<triangle.length; i++) {
    System.out.println(i);
    for(int j=1; j<=i-1; j++) { // [i][0], [i][i]는 구해놨기 때문에 안쪽을 구한다
        result[i][j] = max(result[i-1][j-1],result[i-1][j])+triangle[i][j];
        System.out.println("result["+i+"]["+j+"] = "+result[i][j]);
    }
}

 

 

배열에 잘 들어갔다. 자 이제 마지막 행에서 비교만 하면 된다.

 

answer = -1;
for(int k=0; k<triangle.length; k++){
    if(result[triangle.length-1][k] > answer)
        answer = result[triangle.length-1][k] ;
}

return answer;

 

여기서 시스아웃은 눈으로 잘 들어갔는지 보기위해 출력한거고, 코딩테스트에선 시스아웃을 빼야 정답처리가 된다.