[Programmers] 정수 삼각형

난이도 : Level 3

문제링크

• 꼭대기에서 바닥까지 이어지는 경로 중, 가장 경로의 합이 큰 숫자를 리턴하라
• 대각선 경로만 사용하여 아래로 내려갈 수 있다
• 높이: 1 이상 500 이하
• 정수: 0 이상 9,999 이하

 

해설

• 꼭대기에서 바닥까지 모든 경로의 합 중, 가장 큰 경로의 합을 리턴해야 한다
  • 이전까지의 합이 크더라도 현재 방문하는 정수가 크다면 가장 큰 경로가 될 수 있기 때문
  • 그러나 모든 경로의 합에서 가장 큰 경로를 매번 구하는 것은 비효율적이므로 동적 계획법을 사용한다
• 2차원 정수형 배열을 선언하고 꼭대기에서 (r, c)까지의 최대 경로의 합을 저장한다
  • 경로를 하나씩 늘려가면서 이전에 방문한 점의 가장 큰 누적합을 더하면서 만들어간다
  • 모든 삼각형을 방문하여 dp 배열을 완성한다
• 꼭대기에서 바닥까지 온 경로의 누적합 중, 가장 큰 누적합을 리턴한다

public int solution(int[][] triangle) {        
    int r = triangle.length, c = triangle.length;
    int[][] dp = new int[r][c]; // (r,c) 까지 가는데 최대비용
    dp[0][0] = triangle[0][0];

    for (int i = 1; i < r; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            } else if(j == i) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }

    return Arrays.stream(dp[r-1]).max().getAsInt();
}