99클럽 코테 스터디 21일차 TIL / [프로그래머스] 정수 삼각형

오늘의 학습 키워드

---

DP

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43105

• 플랫폼: 프로그래머스
• 문제명: 정수 삼각형
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int[][] mem = new int[triangle.length][triangle.length];
        mem[0][0] = triangle[0][0];
        
        for(int i=1; i<triangle.length; i++) {
            // row의 가장 왼쪽 컬럼
            mem[i][0] = mem[i-1][0] + triangle[i][0];
            
            // row의 가장 오른쪽 컬럼
            mem[i][i] = mem[i-1][i-1] + triangle[i][i];
            
            // 이외의 중간 컬럼들
            for(int j=1; j<i; j++) {
                mem[i][j] = Math.max(mem[i-1][j-1], mem[i-1][j]) + triangle[i][j];
            }
        }
        
        return Arrays.stream(mem[mem.length-1]).max().getAsInt();
    }
}

접근

• DP로 접근하여 풀이했습니다.
• mem 배열에는 각 위치에 도달할 때까지의 누적합 중 최댓값을 저장합니다.
• 다음으로, row 단위로 mem 배열을 하나씩 채워나갑니다. 이때 고려할 케이스는 3가지입니다.

  1. 행의 가장 왼쪽 컬럼

     도달할 수 있는 경우의 수가 한 가지입니다. (row-1에서 이동하는 경우)

     // row의 가장 왼쪽 컬럼
     mem[i][0] = mem[i-1][0] + triangle[i][0];

  2. 행의 가장 오른쪽 컬럼

     마찬가지로 도달할 수 있는 경우의 수가 한 가지입니다. (row-1, col-1에서 이동하는 경우)

     // row의 가장 오른쪽 컬럼
     mem[i][i] = mem[i-1][i-1] + triangle[i][i];

  3. 이외 중간 컬럼들

     양쪽에서 도달할 수 있습니다. (row-1, col-1), (row-1, col)

     따라서, 값을 비교하여 그 중 큰 수를 취하면 됩니다.

     // 이외의 중간 컬럼들
     for(int j=1; j<i; j++) {
         mem[i][j] = Math.max(mem[i-1][j-1], mem[i-1][j]) + triangle[i][j];
     }

소요 시간

20분