블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 2839번: 설탕 배달을 풀고 작성한 글입니다.
문제
설명
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
풀이
접근법
최대한 많은 수의 5킬로그램 봉지를 사용하고 나머지를 3킬로그램 봉지로 사용하면 될 거라 생각했다.
그래서 5로 나누었는데 되지 않으면 3을 활용하는 방법을 생각했는데 이를 재귀함수로 풀 수 있을 것 같았다.
나의 풀이
처음에는 접근법처럼 아래와 같이 재귀함수를 호출하는 방식으로 문제를 풀었다. 그러나 시간 초과가 되었다.
N: int = int(input())
def recursive_function(N: int, count: int, number: int) -> int:
previous_N: int = N
while N > 0:
if count == -1:
break
elif (N < 5) and (N % 3 != 0):
count -= 1
N = previous_N
count = recursive_function(N=N, count=count, number=3)
elif (N < 5) and (N % 3 == 0):
count += 1
N -= 3
else:
count += 1
N -= number
return count
answer = recursive_function(N=N, count=0, number=5)
print(answer)다른 풀이
이후 다른 if , else 조건 등을 활용하여 재귀함수를 호출하지 않더라도 문제를 푸는 방식을 구상해보다가 결국 시간 내에 풀지 못했다.
다른 사람의 풀이를 봤는데 무척 깔끔하게 해결해서 살짝 허무했다. 앞선 접근법처럼 5의 배수가 되기 전까지 계속해서 3을 빼주다가 5의 배수가 되면 쭉 5로 빼주는 것이다. 문제를 풀며 어려워했던 부분은 해답이 나오지 못해 -1 을 출력해야 하는 경우였는데 이때 N 이 계속해서 3으로 빼져서 0보다 작아지면 결국 답을 구할 수 없는 경우이기 때문에 -1 을 출력하면 됐다.
N: int = int(input())
answer: int = 0
while N > 0:
if N % 5 == 0:
answer += 1
N -= 5
else:
answer += 1
N -= 3
if N < 0:
print(-1)
else:
print(answer)지금 상황에서 가장 탐욕스러운 방법을 선택하는 그리디 알고리즘을 활용해서 문제를 풀 수 있을 것이라 생각해서 무조건적으로 5을 먼저 빼면서 문제를 푸는 방법으로 생각을 했는데 어떻게 하면 5를 최대한 많이 뺄 수 있는 상황을 만들어줄 수 있는지, 그 상황도 꼭 생각해야겠다.
Big-O
주어진 N보다 적은 횟수의 반복이 되는 것은 확실하며 계속해서 빼가며 그 횟수가 줄어들기 때문에 최악의 경우에도 O(N)으로 고려된다. 재귀함수를 호출하는 방식의 경우 최악의 경우를 고민한다고 했을 때 O(N^2)이 되기 때문에 시간초과가 발생한 것 같다.
