[Goorm/Python] 통증 (2) || 구름톤 챌린지 (다이나믹 프로그래밍)

구름톤 챌린지 통증(2) 파이썬

구름LEVEL

❏ 문제 풀이

❍ 문제

구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 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$는 배수 관계가 아니다.

❍ 출력

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

 

❏ 문제 풀이

a < b라는 조건이 있으니, b로 나눠 떨어질 때까지 a를 빼주면 되는 문제이다.

import sys

input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
result = 0
for i in range(n):
    if n % b == 0:
        result += n // b
        n %= b
        break
    if n < a:
        break
    n -= a
    result += 1
		
if n != 0:
    print(-1)
else:
    print(result)

 

❍ 다이나믹 프로그래밍

이 문제는 a, b처럼 2개만 주어지기 때문에, 위와 같은 풀이로 풀이될 수 있지만, 그 이상 많은 개수로 주어졌을 때에는 위처럼 풀이하기란 쉽지 않다.

따라서 중요하게 여겨야 하는 포인트는 $A_p$와 $B_p$는 배수 관계가 아니다. 라는 점이다.

둘이 배수인 경우에는 그리디 알고리즘으로 풀이가 가능하지만, 배수 관계가 아니라면 다이나믹 프로그래밍으로 풀이를 해주어야 한다.

 

< 그리디 알고리즘 - 단위가 배수일 경우 >

[Algorithm] 탐욕(그리디) 알고리즘 || Greedy Algorithm

 

< 다이나믹 프로그래밍 - 단위가 배수가 아닐 경우 >

[Algorithm] DP(Dynamic Programming), 동적 계획법

 

import sys

input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())

# 메모이제이션 (무한대로 초기화)
dp = [float('int')] * (n + 1)
dp[0] = 0

dp는 메모이제이션 즉, 이전에 구한 값이 저장되고 다시 사용할 수 있도록 기록되는 곳이다.

통증 수치가 0이 되기 위해 필요한 최소 개수를 기록하게 된다.

따라서, dp[0]의 경우 0개의 아이템이 필요하다.

 

❍ 점화식

i에 대한 점화식은 $a_i = min(a_{i -a}, a_{i -b}) + 1$을 세워볼 수 있다.

# 0부터 n까지 바텀업 방식
for i in range(n + 1):
    if i >= a:
        dp[i] = min(dp[i], dp[i - a] + 1)
    if i >= b:
        dp[i] = min(dp[i], dp[i - b] + 1)

if dp[n] != float('inf'):
    print(dp[n])
else:
    print(-1)

# print(dp[n] if dp[n] != float('inf') else -1)

0부터 N까지 차례대로 올라가는 바텀업 방식, 반복문을 통해서 최종적으로 dp[n]에 해당하는 값을 구하도록 한다.

점화식을 세웠던 대로 적용해주되, i가 a와 b보다 큰 경우에만 가능하도록 조건문을 추가해주면 된다.

마지막으로 무한대로 초기화를 해뒀던 dp[n]이 inf가 아닌 경우엔 그대로 출력, inf인 경우에는 최소 개수를 구할 수 없었음을 의미하므로 -1을 출력해준다.