# 백준 2039 설탕 배달
n = int(input())
a = n // 3
result = 10000
num = n
while a > -1:
num = n
num -= 3 * a
res = num // 5
if num % 5 == 0:
result = min(result, a + res)
a -= 1
if result == 10000:
print(-1)
else:
print(result)
[문제풀이]
3과 5를 가지고 만들 수 있는 숫자를 일일이 계산해서 풀었다고 보는게 맞겠다.
3으로 최대한 나눌 수 있는 값을 기준으로 하였다
예를 들면 18이라는 숫자를 3으로 최대한으로 뺀다면 6번(= a) 뺄 수 있다
반복문을 통해 3으로 최대한 뺄 수 있는 수를 하나씩 빼가며 a -= 1 하여
a = 5이면 3을 5번 빼기 / 5를 0번 빼기
a = 4이면 3을 4번 빼기 / 5를 1번 빼기
해서 결론적으로
3을 1번 빼기 / 5를 3번 빼기
총 4번 그리고 빼고 난 나머지 또한 0이 되도록 만들기!!
알고리즘 분류를 보니까 다이나믹 프로그래밍이랑 그리디 알고리즘이었다
풀긴 풀었는데 어떤 알고리즘을 이용해서 푼게 아니라 잘 모르겠다....
다시 공부해야 할듯
[파이썬] 백준 1931 회의실 배정 (0) | 2022.03.15 |
---|---|
[백준] 1003 피보나치 함수 (보텀업) (0) | 2022.03.08 |
[백준] 1926 그림 BFS (DFS는 참고만 하기 메모리 초과) (0) | 2022.02.13 |
[파이썬] 백준 1920: 수 찾기 (이진 탐색) (0) | 2021.08.28 |
[파이썬] 백준 2920: 음계 (구현) (0) | 2021.08.28 |