[구름톤 챌린지] 3주차 11일차 통증 (2)

 

 

문제

---

구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 $0$으로 유지하는 것이 중요하다.

게임 안에는 통증 수치를 감소시켜 주는 아이템이 $2$종류가 있다. 아이템의 이름은 $A, B$이고, 각 아이템을 사용 시 각각 $A_p, B_p$만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다.

플레이어는 적과의 전투에서 피해를 입어 현재 $N$의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 $0$으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 $0$보다 작아지는 아이템은 사용할 수 없음에 유의하시오.

입력

---

첫째 줄에 플레이어의 통증 수치를 나타내는 정수 $N$이 주어진다.
둘째 줄에 아이템 $A, B$가 줄일 수 있는 통증 수치 $A_p, B_p$가 공백을 두고 주어진다.

 

 

• $2 \leq N \leq 10^6$
• $2 \leq A_p < B_p \leq 13$
• $A_p$와 $B_p$는 배수 관계가 아니다.

출력

---

플레이어가 통증 수치를 $0$으로 줄이기 위해 필요한 아이템의 최소 개수를 출력한다. 단, 통증 수치를 $0$으로 만들 수 없는 경우에는 -1 을 출력한다.

 

---

문제 접근 방식

---

DP로 접근했다. 바텀업으로 해결했고, DP테이블을 아래와 같이 정의했다.

 

$$DP[i] = i를 \ A와 \ B로 \ 만들었을 \ 때 \ 필요한 \ 아이템의 \ 최소 \ 개수$$

 

그러면 다음과 같은 점화식을 알아낼 수 있다.

 

$$DP[i] = min(DP[i-A], DP[i-B])$$

 

물론 $DP[i-A]$나 $DP[i-B]$가 존재하지 않을 수도 있다. 그런 경우에는 DP[i-A]의 값을 매우 크게 설정함으로써 해결할 수 있다.

 

그 값을 $MAX$라고 하면, 이후에 $DP[N]$의 값이 $MAX$보다 크다면 만들 수 있는지 없는지를 판단할 수 있다. 

 

---

정답 코드

---

# 통증 (2)
import sys
input = sys.stdin.readline

MAX = 1_000_000
N = int(input())
DP = [-1 for _ in range(N+1)]
A, B = map(int, input().rstrip().split())
if A <= N:
    DP[A] = 1
if B <= N:
    DP[B] = 1
for i in range(A+1, N+1):
    a, b = MAX, MAX
    if i == B:
        continue
    if i-A >= 0 and DP[i-A] != -1:
        a = DP[i-A]
    if i-B >= B and DP[i-B] != -1:
        b = DP[i-B]
    DP[i] = min(a, b) + 1
if DP[N] < MAX:
    print(DP[N])
else:
    print(-1)

 

---

특별히 배운 점

---

이 문제는 그리디로도 풀리고, 브루트 포스로도 풀리고, 정수론적 지식을 활용하여 풀 수도 있다. 또한, BFS를 활용하여 풀수도 있다. 이렇듯 풀이가 다양한 문제니 좋은 문제인 것 같다.

 

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

여담으로 이 문제의 확장판이다.