1. 문제와 예제
2. 전체 코드
1) 노가다
# 노가다
kg = int(input())
cnt5 = 0
cnt5 = kg // 5
if kg % 5 == 0:
cnt3 = 0
print(cnt5 + cnt3)
elif kg % 5 == 1:
if cnt5 == 0:
print(-1)
else:
cnt5 -= 1
cnt3 = 2
print(cnt5 + cnt3)
elif kg % 5 == 2:
if cnt5 == 0 or cnt5 == 1:
print(-1)
else:
cnt5 -= 2
cnt3 = 4
print(cnt5 + cnt3)
elif kg % 5 == 3:
cnt3 = 1
print(cnt5 + cnt3)
else:
if cnt5 == 0:
print(-1)
else:
cnt5 -= 1
cnt3 = 3
print(cnt5 + cnt3)
가장 먼저 떠오른 방법이다. 결국 전체 봉지 수를 최소로 가져가려면 5kg 봉지를 최대로 가져가야 한다는 아이디어에서 나온 방법이다. 공통적인 것끼리 묶으면 조금 더 짧게 코드를 만들 순 있겠다.
2) 다이나믹 프로그래밍
# 입력 받기
N = int(input()) # 설탕
res = 0 # 봉지
while N >= 0:
if N % 5 == 0:
res += (N // 5)
print(res)
break
# 5로 나눠지지 않았을 때
N -= 3
res += 1 # 3kg 봉지 하나 추가
else: # while문에서 else가 나왔을 때
print(-1)
1번 방법을 응용하면 다이나믹 프로그래밍이라는 개념이 나온다. 동적계획법이라고도 하며, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 이 개념의 가장 기초인 문제가 되겠다.
3. 풀이
설탕(N)이 5로 나눠질 때까지 '3kg 봉지를 추가하고 설탕에서 3kg를 빼는 작업'을 반복하면 된다. 이 작업을 반복하다가 설탕이 0 아래로 내려갔다면 이는 5kg, 3kg 봉지로는 주어진 설탕을 분배할 수 없다는 의미이므로 -1을 출력한다.
'백준' 카테고리의 다른 글
[백준] 9012번 파이썬 (괄호) (0) | 2024.03.20 |
---|---|
[백준] 4949번 파이썬 (균형잡힌 세상) (0) | 2024.03.20 |
[백준] 2164번 파이썬 (카드2) (0) | 2024.03.20 |
[백준] 1920번 파이썬 (수 찾기) (0) | 2024.03.20 |
[백준] 1018번 파이썬 (체스판 다시 칠하기) (0) | 2024.03.18 |