DP (BOJ 12865) 풀이에 관한 질문

Question

import sys input = sys.stdin.readline n, k = tuple(map(int, input().split())) dp = [0 for _ in range(k+1)] minVal = sys.maxsize for _ in range(n): w, v = tuple(map(int, input().split())) dp[w] = v if w < minVal: minVal = w for i in range(minVal+1, k+1): maxVal = -1 for j in range(minVal, i): maxVal = max(maxVal, dp[j] + dp[i-j], dp[i]) dp[i] = maxVal print(dp[m]) 안녕하세요 강사님! 우선, 이 강의가 저한테 정말 도움이 되고 있음에 감사드립니다!   저는 위와 같이 dp 테이블을 2차원으로 할 생각을 못하고 풀었다가 시간초과가 났습니다. 아직 dp가 어렵게 느껴져서 dp 테이블 설계를 잘 못하겠네요..ㅠㅠ 다행히 강의에서 dp 문제는 올려주신 강의만 제대로 숙지하면 될 것 같다고 하셨는데 dp 문제를 잘 풀기 위한 다른 팁 같은게 있을까요?

알리 Ally · Answer

안녕하세요, Taejin Kim님! 비슷한 질문이 있어, 해당 글을 참고하시면 도움이 될 것 같습니다! ( 링크 ) 보시고, 추가적으로 궁금하신 점이나 다른 질문 있으시면 남겨주세요!

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. Taejin Kim님께서 DP(동적 계획법) 문제에 대해 고민하고 계시는 것 같습니다. 특히 BOJ 12865 문제를 푸시다가 시간 초과 문제를 겪으신 것 같네요. 주신 코드에 대해 몇 가지 피드백과 함께 DP 문제를 잘 풀기 위한 팁을 안내드리겠습니다. 먼저, 주신 코드를 보니 일차원 배열을 활용하여 해결을 시도하셨지만, 두 가지 이유로 인해 문제가 발생할 수 있습니다: 직관적이지 않은 접근 : DP 테이블 설계를 시도하셨지만, 보다 직관적으로 이해할 수 있도록 이차원 배열을 고려하는 것이 필요할 수 있습니다. 특히, 물건의 무게와 가치를 모두 고려한 해결법을 더 간단히 구현할 수 있습니다. 점화식의 혼동 : 코드 내에서 maxVal을 갱신하는 과정이 다소 복잡하게 진행되었습니다. 보통 이 문제는 물건을 담을지 말지를 결정하면서 가치를 더한 새로운 값이 기존의 값보다 큰지를 비교하고 결정합니다. DP 문제를 잘 풀기 위한 팁: DP 테이블 정의하기 : DP 배열의 각 인덱스가 무엇을 의미하는지 명확히 정의하세요. 예를 들어, dp[i] 가 i 무게 내에서의 최대 가치를 의미할 수 있습니다. 점화식 수립 : 문제의 요구사항에 맞는 점화식을 되풀이하여 설정해 보세요. 이 과정에서 DP 관계식을 수립하는 데 핵심적인 인사이트가 포함됩니다. 작은 예제를 통하여 점화식을 수립해 보고, 그 타당성을 확인하세요. 작은 문제부터 시작하기 : 작은 문제부터 시작해 점점 복잡하게 키워가세요. DP는 작은 문제의 답을 이용하여 더 큰 문제의 답을 구하는 식으로 진화합니다. 다양한 문제 풀어보기 : 강의에서 제공된 예제뿐만 아니라, 여러 문제를 풀어보며 경험을 축적하세요. 다양한 유형의 DP 문제를 풀어보면 생각의 폭이 넓어집니다. 참고 자료 활용 : 블로그나, 여러 온라인 플랫폼에서 다른 해결법을 읽고 이해하는 방법도 좋습니다. 다른 사람의 사고 과정을 따라가며 배우는 것도 좋은 연습입니다. 아래는 유사한 문제에 관한 설명을 볼 수 있는 링크입니다: - “BOJ6603질문있습니다!” - 다르고 유사한 문제들을 푸는 사고 과정을 총체적으로 설명합니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.