정수 삼각형 (프로그래머스) [JAVA]

 

 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

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

입출력 예

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

 

풀이

전형적인 동적 프로그래밍 방식으로 풀었다. Bottom-up 방식으로 맨 밑에서부터 생각했는데, 배열의 위치상 경로는 아래, 혹은 아래 오른쪽만 가능하므로 식을 간단하게 적어보면
$Path[x][y] = max(Path[x-1] [y],Path[x-1] [y-1]) + triangle[x][y]$ 로 할 수 있다.
이때 밑에서 부터 시작하므로 Path[x-1] [y-1], Path[x-1] [y] 역시 재귀호출을 통해 채워줘야 한다.
이때 x와 y의 범위도 지정해서 불필요한 연산을 줄이고 findPath()메소드를 계속 재귀호출을 하며 cache에 값을 채워 넣는 방식으로 문제를 해결하였다.

 

코드

class Solution {
	static int cache[][];
	
    public int solution(int[][] triangle) {
        int max = 0;     
        init(triangle.length, triangle[0][0]);
        for(int i=0; i<triangle.length; i++) {
        	max  = Math.max(findPath(triangle.length-1, i, triangle), max);
        }
        //print(triangle.length);
        //System.out.println(max);
        return max;
    }
    
    public void init(int n, int start) {
    	cache = new int[n][n];
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n; j++) {
    			cache[i][j] = -1;
    		}
    	}
    	cache[0][0] = start;
    }
    
    public void print(int n) {
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n; j++) {
    			System.out.print(cache[i][j] + " ");
    		}
    		System.out.println("\n");
    	}
    }
    
    public int findPath(int x, int y, int[][] triangle) {
    	
    	if(cache[x][y] != -1) return cache[x][y];
    	if(x > 0  && y < x && y > 0) {
    		cache[x][y] = Math.max(findPath(x-1, y, triangle),findPath(x-1, y-1, triangle)) + triangle[x][y];
        	return cache[x][y];
    	}
    	else if(y == x) {
    		cache[x][y] = findPath(x-1, y-1, triangle) + triangle[x][y];
    	}
    	else if(y == 0) {
    		cache[x][y] = findPath(x-1, y, triangle) + triangle[x][y];
    	}
    	return cache[x][y];
    }
}

 

결과