문제📖
- 첫째 줄에 N을 입력받는다.
- 봉지는 3, 5만 존재.
- N을 3, 5로 만들 수 없다면 -1 출력.
- 봉지갯수를 최소한으로!
풀이🙏
문제를 처음에 봤을땐 상당히 쉬워보였지만 생각보다 까다로운 문제였다.
- 18 -> 4 (3으로 딱 나뉘었을시로 설정하면 6으로나오므로 실패)
- 11 -> 3 (3과 5를 적절히 사용해서 만들 수 있어야함)
일반적인 3과 5의 배수로 만든다면 if 3%==0 and 5%==0 으로 하면되겠지만 11은 딱 떨어지진않는다.
하지만 입력받은 수를 3보다 작아질때까지 계속 3으로 빼준다면?
11 -> 8 -> 5 (5로 딱 나뉘어짐!!)
why? 5로 빼지않고 3으로 빼는가?? 11-5 ==6(3으로 바로 나뉘어질텐데?)
이유는, 3 과 5로 둘 다 나뉘어지는 15와 같은수는 5로 나누는게 봉지갯수를 최소한으로 하기때문에 나누는건 5로 고정한 상태에서 가변변수는 3으로 설정하는것이다 ✌️
코드💻
# boj, 2839 : 설탕 배달, python3
N = int(input())
result = 0
while True :
if N % 5 == 0 :
result += (N // 5)
print(result)
break
N -= 3
result += 1
if N < 3 :
print(-1)
break결과😎
출처📝
https://www.acmicpc.net/problem/2839
풀코드
