Programmers[43105] - 정수 삼각형[Level3]

링크

Programmers[43105]

문제설명

• 정수 삼각형

문제풀이

• 완전탐색으로 가면 시간 너무 오래걸림
• DP로 제일 유리한 경로만 따라가면서 효율적으로 풀이
• arr[i][j] = max(arr[i-1][j-1],arr[i-1][j])

문제코드

import java.util.Arrays;

class Solution {
    public static int solution(int[][] triangle) {
            int answer = 0;
            int len = triangle.length;
            for (int i = 1; i < len; i++) {
                for (int j = 0; j <= i; j++) {
                    if(j==0) {
                        triangle[i][j]=triangle[i][j]+triangle[i-1][j];
                    }
                    else if(j==i) {
                        triangle[i][j]=triangle[i][j]+triangle[i-1][j-1];
                    }
                    else {
                    triangle[i][j] = Math.max(triangle[i][j]+triangle[i-1][j-1],triangle[i][j]+triangle[i-1][j]);
                    }
                }
            }
            for(int i : triangle[len-1]) {
                answer = Math.max(answer, i);
            }

            return answer;
        }
}

아쉬운점

Input 형태(Arrays.toString())

• Input(2차원 배열 int)을 서툴게 다룸

  • 이클립스에서 코딩&디버그 시도 하려는 데에 시간이 걸림

  • public static void main(String[] args) {
        solution(new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}});
    }

    이렇게 하면 됨

• 완전탐색으로 풀려고 접근했었음 - 시간 오래걸림 DP로 해야할 필요

• 경계처리를 제대로 안해서 에러남

• Index 생각 꼼꼼히 안해서 제일 오른쪽 원소가 Update가 안됬음

  • for (int i = 1; i < len; i++) {
            for (int j = 0; j <= i; j++) {
            }
    }

• Arrays.sort(오름차순) 내림차순 하는 방법 모름

  • Arrays.sort(arr , Collections.reverseOrder());
    에러가 일어납니다. Collections.reverseOrder()의 경우 ,int[] 배열 을 정렬 할 수 업습니다.
    출처: https://minaminaworld.tistory.com/70 [미나미 블로그]

    이렇다고 한다

  • 그냥 sort 한 후 arr[len-1]하거나 Max로 하면 된다.

잘한점

• 파이썬으로 풀었었는데 java로 다시 품
• Programmers java input 형식 공부함