[프로그래머스] 정수 삼각형 43105 (JAVA)

풀이방식

상단부

1. 2층부터 마지막층까지 순회
2. 층내에서 왼쪽 -> 오른쪽으로 이동하면서 부모 노드 값을 선택해서 더함
3. 맨 왼쪽인 경우, 부모 노드도 맨 왼쪽 노드
4. 맨 오른쪽인 경우, 부모 노드도 맨 오른쪽 노드
5. 중간에 있는 경우, 부모 노드는 둘 중에 더 큰 것을 선택

하단부

1. 연산이 끝난 마지막 층의 값들을 검사함
2. 가장 큰 값을 답으로 함

고민과정

시간복잡도 오류 코드

완전탐색, 상향식 top-down

기준 위치에서 다음으로 넘어갈 때 오른쪽 아래, 왼쪽 아래 중 선택
가장 마지막까지 선택했을 때 더 큰 값을 갖는 것을 그 앞의 호출로 리턴
마지막 층에서부터 리턴 결과가 올라옴

public class NUM43105 {
    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution(triangle));
    }
    public static int solution(int[][] triangle) {
        int answer = 0;
        answer = chooseNext(triangle, 0, 0, 0);

        return answer;
    }

    public static int chooseNext(int[][] triangle, int row, int col, int sum) {
        int num = triangle[row][col];
        sum += num;

        if(row >= triangle.length-1) {
            return sum;
        }

        return Math.max(chooseNext(triangle, row+1, col, sum), chooseNext(triangle, row+1, col+1, sum) );
    }
}

문제

• 비효율적인 연산(같은 계산 여러 번 수행), 느린 속도

형제 노드에서 아래 노드로 이동할 때 같은 노드를 선택할 수 있다
연산 결과를 저장해둔다면 같은 노드를 선택하는 경우에 대해서 한 번만 연산하면 된다

해결법

• 동적 계산법 활용 (메모리를 추가하여 같은 연산 결과를 가져다 사용)

구현

동적계획법, 하향식 bottom-up

위에서부터 내려가면서 해를 저장해나감

public class NUM43105 {
    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution(triangle));
    }
    
    public static int solution(int[][] triangle) {
        int answer = 0;

        for(int r = 1; r < triangle.length; r++) {
            for(int c = 0; c < triangle[r].length; c++) {
                if(c == 0) triangle[r][c] += triangle[r-1][c];
                else if (c == triangle[r].length-1) triangle[r][c] += triangle[r-1][c-1];
                else triangle[r][c] += Math.max(triangle[r-1][c-1], triangle[r-1][c]);
            }
        }

        for(int c = 0; c < triangle[triangle.length - 1].length; c++) {
            if(triangle[triangle.length-1][c] >= answer) answer = triangle[triangle.length-1][c];
        }

        return answer;
    }

---

*다른 분들의 코드를 참고하여 작성했습니다