상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
풀이 방식
입력 제한 5000에 시간 1초이면 O(N^2)은 간당간당하다. 이를 염두하여 최대한 O(N) 또는 O(NlogN)으로 풀도록 해야 한다.
1번 풀이: 틀렸습니다.
'''
11 = 5 + 3 + 3
3 3
5 2
'''
N = int(input())
answer = float('inf')
for i in range(N//5+1):
# 5kg가 i개인 경우
if i == 0 :
if N % 3 == 0:
answer = N//3
continue
continue
rest = N-(5*i)
if rest % 3 == 0:
answer = min(answer, i + rest//3)
print(answer)
내가 처음에 생각한 풀이는 숫자가 더 큰 5kg 짜리를 0개인 경우, 1개인 경우, ... N/5개인 경우 에 대하여 각각 나올 수 있는 3kg 짜리 갯수와 더한 값 중 min을 취하는 것이었다.
로직은 맞았지만 정확하게 Nkg을 만들 수 없으면 -1을 출력하는 부분을 빠트렸다.
2번 풀이: 성공
'''
11 = 5 + 3 + 3
3 3
5 2
'''
N = int(input())
answer = float('inf')
for i in range(N//5+1):
# 5kg가 i개인 경우
if i == 0 :
if N % 3 == 0:
answer = N//3
continue
continue
rest = N-(5*i)
if rest % 3 == 0:
answer = min(answer, i + rest//3)
if answer == float('inf'): print(-1)
else: print(answer)
정확하게 N킬로를 만들 수 있는 경우가 나오지 않으면 answer 변수가 업데이트되지 않기 때문에 해당 값이 inf이면 -1을 출력하도록 하였다.
DP를 사용한 다른 풀이
해당 문제는 최적화 문제로 DP를 고려할 수도 있는 문제이다.
Nkg의 설탕에 대해 최소 갯수를 memo한다고 하자.
N = int(input())
dp = [5001] * (N+3)
dp[3] = dp[5] = 1
for i in range(6, N+1):
dp[i] = min(dp[i-3], dp[i-5]) + 1
print(dp[N] if dp[N] < 5001 else -1)
초기 3kg과 5kg은 무조건 1개이기 때문에 이 두 가지 경우를 base case로 잡고 계산을 진행하며 나머지 배열의 값에는 입력 제한인 5000보다 1큰 5001로 초기화 시켜 준다.
3~N킬로그램까지 bottom-up 방식으로 각 kg에서 가장 적은 양의 봉지를 저장하고 해당 값들은 5kg, 3kg 중 어느 것을 담아야 최소인지를 구하여 해당 값에 1을 더하는 식으로 구현한다.
7kg의 경우 5kg, 3kg 모두 5001의 값을 가지고 있어 5002로 초기화되기 때문에 해당 반례를 주의해야 한다.
이 문제의 입력은 그렇게 크지 않아 브루트포스와 DP 간의 시간 차이가 크지 않지만 N의 범위가 특정 임계값 이상 커지면 브루트포스로는 풀리지 않을 것이다.
