[DP] 특정한 숫자를 만드는 DP 유형

PS/알고리즘

[DP] 특정한 숫자를 만드는 DP 유형

행복한라이언 2024. 2. 14. 17:00

728x90

1. 대표 유형

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

item → 2차원DP의 행을 의미	weight → 2차원DP의 열을 의미	value → DP에 들어갈 값
동전	원(금액)	개수(1이 default)
보석	무게	가치
퀘스트	경험치	시간

2. 유형에 따른 포인트

★★ 유형1. 조합한 동전이 같다면 순서가 달라도 같은 경우 vs 순서가 다르면 다른 경우
- 순서가 다르면 다른 경우 ▷ dp의 기본 유형 '타일 문제'처럼 생각하면 된다. 그 전의 동전 상태는 궁금하지 않고 현재 어떤 동전 써서 어떤 weight를 만들지가 더 중요하다. 그래서 그냥 dp기초 문제처럼 생각하면 세상 쉽게 풀린다.
- 순서가 달라도 같은 경우 ▷ 보통 대부분 '순서가 달라도 같은 유형'이 전제되어 있다. 동전의 촤소 개수, 최대 가치, 최소 시간을 궁금해하기 때문에 그렇다. 그래서 유형2, 유형3 은 보통 '순서가 달라도 같은 유형'을 전제로 한다.
★★★★★ 유형2. 주어진 item을 중복 사용(정수배) 할 수 있는가?
- 중복해서 사용할 수 있는 경우 ▷ '앞'에서부터 본다.
- 중복해서 사용할 수 없는 경우 ▷ '뒤'에서부터 본다.
★★★★★ 유형3. DP의 열을 의미하는 weight를 특정할 수 있는가?
- 동전처럼 '목표 금액'이 존재한다면 열은 0원부터 ~ 목표금액까지 생성하면 된다. 그런데 만약에 m원 이상 만들 동전의 최소 개수를 구하라고 하는 문제는 어떻게 될까? '금액'을 기준으로 '열'을 구성할 수 없다. 있다하더라도 메모리초과가날 것이다.
- 따라서 weight라고 설정한 것이 정확히 얼마까지인지 판단하기 어렵고 문제에서 제시한 조건에 매우 크다면 열(weight)과 값(value)을 바꿔서 생각할 필요가 있다.
- 정리
  - weight의 값을 특정할 수 없는 경우 ▷ 기존의 weight를 value로, value를 weight로 변경한다.
★ 유형4. 만들 수 있는 동전의 경우의 수 vs 동전의 수
- '동전의 수' 유형에서는 0원의 경우, 0이다.
- '동전의 경우의 수'유형에서는 0원의 경우, 1이다.
- 5원의 동전이 1개가 있을 때, 5원을 만드는 동전의 수는 dp[5] = dp[5 - 5] + 1(동전 하나 추가) = 1 (∵ dp[0] = 0)
- 5원의 동전이 1개가 있을 때, 5원을 맏느는 동전의 경우의 수 dp[5] = dp[5 -5] = dp[0] = 1
위 문제 유형은 탑다운보다 바텀업 풀이가 더 기억하기 쉽기 때문에 바텀업으로 풀도록하자.