[python] 백준 - 2839 (설탕 배달)
실버 4 문제이며 제한 시간은 1초이다.
문제
해결 과정
이 문제는 그리디, DP 두 가지 방식으로 해결해봤다.
그리디
그리디 측면에서 생각해보면 5kg 봉지를 최대한 많이 사용하는 것이 제일 적은 개수의 봉지를 배달하는 방법이다. 따라서 3kg봉지로 하나씩 담으면서 남은 설탕의 양이 5로 나누어 떨어지면 그 양은 5kg 봉지로 담을 수 있는 최대의 양이 된다.
최종적으로 n이 0이 아니면 나누어 떨어지지 않는다는 것이므로 -1을 출력해준다.
n = int(input())
answer = 0
while n > 0:
if n % 5 == 0:
answer += n // 5
n %= 5
break
n -= 3
answer += 1
print(answer if n == 0 else -1)DP
DP로 해결하는 방식은 현재 나의 위치에서 -3번째와 -5번째를 비교해서 더 적은 봉지를 사용한 곳에서 3kg봉지 혹은 5kg 봉지를 사용해서 담는 것이 최소한의 봉지를 사용하는 것이 된다.
dp[n]이 0이라면 나누어 떨어지지 않는 것이므로 -1을 출력해준다.
n = int(input())
dp = [0] * (n + 1)
dp[3] = 1
if n >= 5:
dp[5] = 1
for i in range(5, n + 1):
if dp[i - 3] > 0:
if dp[i] == 0:
dp[i] = dp[i - 3] + 1
else:
dp[i] = dp[i] if dp[i] < dp[i - 3] + 1 else dp[i - 3] + 1
if dp[i - 5] > 0:
if dp[i] == 0:
dp[i] = dp[i - 5] + 1
else:
dp[i] = dp[i] if dp[i] < dp[i - 5] + 1 else dp[i - 5] + 1
print(dp[n] if dp[n] > 0 else -1)
댓글
0아직 댓글이 없습니다.