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

Question

오름차순 정렬 후에 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); }

김태원 · Answer

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

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 임인혁님, 질문 주셔서 감사합니다. 질문 주신 코드에서 벽돌을 내림차순으로 정렬하고, 동적 프로그래밍(DP) 배열을 활용하여 각 벽돌이 가장 아래에 있는 경우의 최대 높이를 계산하셨네요. 질문 주신 방식대로 접근하시면 문제 없이 풀이가 가능합니다. 여기서는 각 벽돌이 가장 아래에 위치할 경우를 가정하며, 이를 기반으로 이전 벽돌 중 무게가 더 큰 것들에 대해 가능한 최대 높이를 갱신하는 방식입니다. 결국 최종적으로 maxHeight 에는 가능한 최대 탑의 높이가 저장됩니다. 이 방식은 전형적인 DP 접근 방식으로, 각 상태의 최대값을 계산하고 이전 상태의 값을 재활용하여 문제를 해결합니다. 다만, 무게나 면적을 기준으로 정렬한 뒤에 로직을 수행하는 것이 좀 더 정확할 수 있습니다. 여기서는 무게를 기준으로 비교하셨기 때문에 적절한 순서로 정렬되어 있다면 문제가 없습니다. 관련된 질문을 한 번 참고해보시길 바랍니다. 선생님 질문이 있습니다.. 이 질문에서 질문자는 DP 배열을 사용하여 탑의 최대 높이를 계산하는 로직을 점검하고 있습니다. 이와 비슷한 접근 방식으로 자신의 코드를 검토하고, 그것이 의도한 대로 작동하는지 점검하는 과정을 확인할 수 있습니다. 혹시 추가적인 설명이나 도움이 필요하시면 언제든지 추가 질문을 주시기 바랍니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.