CodeWars 아흔 네 번째 문제

Pyramid Slide Down

class Slide{
	int number;
	int row;
	int col;
}

public class LongestSlideDown {

    public static int longestSlideDown(int[][] pyramid) {
    	
    	Slide[] sum = new Slide[1];
    	sum[0] = new Slide();
    	sum[0].number = pyramid[0][0];
    	sum[0].row = 0;
    	sum[0].col = 0;
    	
    	Slide[] result = slideDown(pyramid, sum, 1);
    	
    	return findMax(result);
    }

	private static int findMax(Slide[] result) {
		
		int max = 0;
		
		for(int i = 0; i < result.length; i++) {
			if(result[i].number > max) {
				max = result[i].number;
			}
		}
		
		return max;
	}

	private static Slide[] slideDown(int[][] pyramid, Slide[] sum, int row) {
		
		if(row == pyramid.length) {
			return sum;
		}
		
		Slide[] newSum = new Slide[(int)Math.pow(2, row)];

		for(int i = 0, j = 0; i < sum.length; i++) {
			newSum[j] = new Slide();
			newSum[j].number = sum[i].number + pyramid[sum[i].row + 1][sum[i].col]; // 왼쪽
			newSum[j].row = sum[i].row + 1;
			newSum[j].col = sum[i].col;
			j++;
			newSum[j] = new Slide();
			newSum[j].number = sum[i].number + pyramid[sum[i].row + 1][sum[i].col+1]; // 오른쪽
			newSum[j].row = sum[i].row + 1;
			newSum[j].col = sum[i].col + 1;
			j++;
		}
		
		return slideDown(pyramid, newSum, row+1);
	}
}

• 이번 문제는 성공하지 못했다.
• 일단 기본적으로 나는 완전 탐색을 생각했다. 최종 나올 수 있는 모든 결과 값 중에 최대 값을 찾으려고 했다.
• 물론 내가 짠 코드는 15 행까지 정도는 가능하다. 그러나… 행이 엄청 커진다면 TIME OUT이 발생한다.
• 6시간 이상 풀다가 지쳐서 결국 BEST 코드를 보기로 했다.
• BEST 코드는 역시 BEST였다.
• 나는 처음부터 내려가는 것을 생각했으나 BEST 코드의 경우 아래에서 위로 올라오는 것을 생각했다.
• 즉, 밑에서 올라갈때는 두 개의 수는 위 행의 하나의 수로 귀결된다. 이때 위 행의 수와 합쳐서 더 큰 수를 더해가면 된다.
• 그렇게 되면 위에서 더 크게 더해지는 수들이 올라 오다보면 결국 첫째항은 최대 값이 나오게된다.
• 이번 문제를 통해 또 재미난 알고리즘을 배우게 되었다.

Best Code

for (int i = p.length - 1; i >= 1; i--)
    for (int j = 0; j < i; j++)            
        p[i - 1][j] += Math.max(p[i][j], p[i][j + 1]);

return p[0][0];