DP 가장 높은 탑 쌓기: 내림차순 정렬

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

4. 가장 높은 탑 쌓기(LIS 응용)

작성

오름차순 정렬 후에 dy에는 해당 인덱스의 벽돌이 가장 밑에 있을 경우로 생각해서 코드를 작성 했는데 제 논리에서는 엣지 케이스가 없는데 이런 아이디어로 dp를 풀어도 괜찮을까요?

dp에는 자신이 가장 아래 있을 경우에 가장 높은 높이를 넣어줬고 내림차순이니 앞에 인덱스보다 무게가 더 높다면 해당 인덱스의 높이를 현재 인덱스의 벽돌에 올릴 수 있다는 생각으로 문제 풀이에 접근 했습니다.

public void solution(int[][] arr, int n) {
    Arrays.sort(arr, Comparator.comparingInt((int[] a) -> a[0]));

    int[] dy = new int[n];
    dy[0] = arr[0][1];
    int maxHeight = dy[0];

    for (int i = 1; i < n; i++) {
        int height = arr[i][1];
        int weight = arr[i][2];
        int mh = height;

        for (int j = i - 1; j >= 0; j--) {
            if (weight > arr[j][2]) {
                mh = Math.max(mh, height + dy[j]);
            }
        }

        dy[i] = mh;
        maxHeight = Math.max(maxHeight, mh);
    }

    System.out.println(maxHeight);
}

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

벽돌들을 오름차순으로 정렬하고, i 번째 벽돌을 지금까지 만들어진 탑들의 맨 밑에 넣는 구조의 다이나믹도 논리상 문제가 없습니다.

잘 하신 코드입니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 임인혁님, 질문 주셔서 감사합니다.

질문 주신 코드에서 벽돌을 내림차순으로 정렬하고, 동적 프로그래밍(DP) 배열을 활용하여 각 벽돌이 가장 아래에 있는 경우의 최대 높이를 계산하셨네요. 질문 주신 방식대로 접근하시면 문제 없이 풀이가 가능합니다.

여기서는 각 벽돌이 가장 아래에 위치할 경우를 가정하며, 이를 기반으로 이전 벽돌 중 무게가 더 큰 것들에 대해 가능한 최대 높이를 갱신하는 방식입니다. 결국 최종적으로 maxHeight에는 가능한 최대 탑의 높이가 저장됩니다.

이 방식은 전형적인 DP 접근 방식으로, 각 상태의 최대값을 계산하고 이전 상태의 값을 재활용하여 문제를 해결합니다. 다만, 무게나 면적을 기준으로 정렬한 뒤에 로직을 수행하는 것이 좀 더 정확할 수 있습니다. 여기서는 무게를 기준으로 비교하셨기 때문에 적절한 순서로 정렬되어 있다면 문제가 없습니다.

관련된 질문을 한 번 참고해보시길 바랍니다.

선생님 질문이 있습니다..

이 질문에서 질문자는 DP 배열을 사용하여 탑의 최대 높이를 계산하는 로직을 점검하고 있습니다. 이와 비슷한 접근 방식으로 자신의 코드를 검토하고, 그것이 의도한 대로 작동하는지 점검하는 과정을 확인할 수 있습니다.

혹시 추가적인 설명이나 도움이 필요하시면 언제든지 추가 질문을 주시기 바랍니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

DP 가장 높은 탑 쌓기: 내림차순 정렬