99클럽 코테 스터디 21일차 TIL + 정수 삼각형 (java)

 

💡 문제

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

권장 시간

• 1시간 30분

소요 시간

• 50분

나의 풀이 코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) { // 제일 왼쪽 줄
                    triangle[i][j] += triangle[i-1][j];
                }
                else if (i == j) { // 제일 오른쪽 줄
                    triangle[i][j] += triangle[i-1][j-1];
                } else { // 중간 줄들
                    triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
                }
                
                answer = Math.max(answer, triangle[i][j]);
            }
        }
    
        return answer;
    }
}

주요사항

DP 문제는 처음 풀어봤는데 생각보다 재밌었다!

규칙이 확실하게 있는게 좋달까..

근데 프로그래머스에서 채점하면 정확성 64.3 / 효율성 35.7로 너무 낮게 나와서 어떻게 개선할 수 있을지 고민… 나중에 알고 스터디하면 물어봐야겠다.

Ref.

동적계획법(Dynamic Programming)