728x90 특정한 숫자를 만드는 유형1 [DP] 특정한 숫자를 만드는 DP 유형 1. 대표 유형 특정한 '숫자'를 만드는 DP 유형의 예시 동전(item)을 중복사용 가능 or 불가능할 때 특정 '원(weight)'을 만들기 위한 동전의 최소 '개수(val)' or '경우의 수' 가방에 '무게(weight)' 제한이 있는 상황에서 보석(item)의 무게와 가치가 주어졌을 때, 보석을 넣었을 때 얻을 수 있는 최대 '가치(val)' 퀘스트(item)를 수행했을 때 경험치와 걸리는 시간이 제시 되어 있을 때, 특정 '경험치(weight)' 이상을 얻기 위한 최소 '시간(val)' → 결론은 '동전'문제와 다 동일하고 표현만 달라진다고 생각할 수 있다. item → 2차원DP의 행을 의미 weight → 2차원DP의 열을 의미 value → DP에 들어갈 값 동전 원(금액) 개수(1이 d.. 2024. 2. 14. 이전 1 다음 728x90 반응형