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

 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 문제를 잘 풀기 위한 다른 팁 같은게 있을까요?

안녕하세요, 인프런 AI 인턴입니다.

Taejin Kim님께서 DP(동적 계획법) 문제에 대해 고민하고 계시는 것 같습니다. 특히 BOJ 12865 문제를 푸시다가 시간 초과 문제를 겪으신 것 같네요. 주신 코드에 대해 몇 가지 피드백과 함께 DP 문제를 잘 풀기 위한 팁을 안내드리겠습니다.

먼저, 주신 코드를 보니 일차원 배열을 활용하여 해결을 시도하셨지만, 두 가지 이유로 인해 문제가 발생할 수 있습니다:

직관적이지 않은 접근: DP 테이블 설계를 시도하셨지만, 보다 직관적으로 이해할 수 있도록 이차원 배열을 고려하는 것이 필요할 수 있습니다. 특히, 물건의 무게와 가치를 모두 고려한 해결법을 더 간단히 구현할 수 있습니다.
점화식의 혼동: 코드 내에서 maxVal을 갱신하는 과정이 다소 복잡하게 진행되었습니다. 보통 이 문제는 물건을 담을지 말지를 결정하면서 가치를 더한 새로운 값이 기존의 값보다 큰지를 비교하고 결정합니다.

DP 문제를 잘 풀기 위한 팁:

DP 테이블 정의하기: DP 배열의 각 인덱스가 무엇을 의미하는지 명확히 정의하세요. 예를 들어, dp[i]가 i 무게 내에서의 최대 가치를 의미할 수 있습니다.
점화식 수립: 문제의 요구사항에 맞는 점화식을 되풀이하여 설정해 보세요. 이 과정에서 DP 관계식을 수립하는 데 핵심적인 인사이트가 포함됩니다. 작은 예제를 통하여 점화식을 수립해 보고, 그 타당성을 확인하세요.
작은 문제부터 시작하기: 작은 문제부터 시작해 점점 복잡하게 키워가세요. DP는 작은 문제의 답을 이용하여 더 큰 문제의 답을 구하는 식으로 진화합니다.
다양한 문제 풀어보기: 강의에서 제공된 예제뿐만 아니라, 여러 문제를 풀어보며 경험을 축적하세요. 다양한 유형의 DP 문제를 풀어보면 생각의 폭이 넓어집니다.
참고 자료 활용: 블로그나, 여러 온라인 플랫폼에서 다른 해결법을 읽고 이해하는 방법도 좋습니다. 다른 사람의 사고 과정을 따라가며 배우는 것도 좋은 연습입니다.

아래는 유사한 문제에 관한 설명을 볼 수 있는 링크입니다:
- “BOJ6603질문있습니다!” - 다르고 유사한 문제들을 푸는 사고 과정을 총체적으로 설명합니다.

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

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

DP 문제를 잘 풀기 위한 팁: