[99클럽 코테 스터디 11일차 TIL] 동적계획법

📖 오늘의 학습 키워드
동적계획법

오늘의 회고

문제

[정수 삼각형]
https://school.programmers.co.kr/learn/courses/30/lessons/43105

나의 해결

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        for(int level = 1; level < triangle.length; level++){
            triangle[level][0] += triangle[level-1][0];
            triangle[level][triangle[level].length-1] += triangle[level-1][triangle[level-1].length-1];
            for(int idx = 1; idx < triangle[level].length-1; idx++){
                triangle[level][idx] += Math.max(triangle[level-1][idx-1], triangle[level-1][idx]);
            }
        }
        for(int i = 0; i < triangle[triangle.length-1].length; i++) {
            answer = Math.max(answer, triangle[triangle.length-1][i]);
        }
        return answer;
    }
}

1. 삼각형을 위에서 아래로 내려가면서 각 지점에서의 최댓값을 구한다.
2. 한 칸을 기준으로 대각선 왼쪽 위의 값과 오른쪽 위의 값을 구해 둘 중 최댓값을 해당 칸의 값과 더한다.
   • 각 층의 처음 칸은 왼쪽 위가 없고 마지막 칸은 오른쪽 위가 없으므로 둘은 각각 오른쪽 위, 왼쪽 위의 값과 더한 값을 저장한다.
   • 두 번째부터 끝에서 두 번째 칸의 경우 대각선 왼쪽 위 칸의 값 triangle[level-1][idx-1]과 대각선 오른쪽 위 칸의 값 triangle[level-1][idx] 중 큰 값과 더해 저장한다.
3. 제일 아래층 칸들을 돌며 최댓값을 찾아 answer에 저장하고 이를 반환한다.

새로 학습한 내용

불필요한 연산을 포함하는 코드를 수정해서 실행 시간을 줄일 수 있었다. 앞으로는 테스트를 통과한 이후에도 실행 시간 단축을 위해 코드를 수정하고 발전해 나가야겠다.