728x90 동전 거슬러주기2 [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. [DP] 아이템을 적절히 고르는 문제 / 동전 거슬러주기 문제링크 https://www.codetree.ai/missions/2/problems/coin-change?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 동전 거슬러주기 유형 중 같은 동전을 중복해서 줄 수 있는 유형 Top-down의 핵심은 점화식이며 내가 설정한 숫자들의 의미를 잘 부여야한다. ret = inf dpf(money) = min(ret, dpf(money - coin) + 1) where coin dp[0]은 impossible이 아니다. # -1: no.. 2024. 2. 5. 이전 1 다음 728x90 반응형