Algorithm/(Java) PS

[Programmers] 정수 삼각형

noahkim_ 2023. 9. 22. 20:44

난이도 : 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();
}

 

'Algorithm > (Java) PS' 카테고리의 다른 글

[Programmers] 등굣길  (0) 2023.09.23
[Programmers] 사칙연산  (0) 2023.09.23
[Programmers] N으로 표현  (0) 2023.09.22
[Programmers][Kakao] 캠핑  (0) 2023.09.21
[Leetcode Top Interview 150] 128. Longest Consecutive Sequence  (2) 2023.09.17