그리디 문제이다. 이 문제의 핵심은 '5킬로그램짜리 봉지를 최대한 많이 사용하는 것'이다.
설탕을 3kg와 5kg짜리 봉지로 나누는 방법: 2 가지 경우
1) 설탕 무게(N)가 5kg으로 나누어 떨어지는 경우
이때는 5kg짜리 봉지만 사용하면 되므로, N을 5로 나눈 몫을 구하면 된다.
예) 25를 나눌 때: 25 / 5 = 5
2) 설탕 무게(N)가 5kg으로 나누어 떨어지지 않는 경우
이때는 N이 5로 나누어 떨어질 때까지, N에서 3을 빼준다.
만약 반복적으로 3을 빼다가, 5의 배수가 나오면 5로 나눠준다.
예)21킬로그램의 설탕을 나눌 때: 21-3-3=15, 15 / 5 = 3
만약 반복적으로 3을 빼다가, 음수가 나오면 3과 5로 만들 수 없는 수이므로 -1을 출력한다.
예)22킬로그램의 설탕을 나눌 때: 22-3-3-3-3-3-3-3-3 = -2
만약 반복적으로 3을 빼다가, 0이 나오면 N은 3으로 나누어 떨어지는 수이다.
예)21kg의 설탕을 나눌 때: 21-3-3-3-3-3-3-3=0
추가적인 연산 없이 반복문을 종료한다.
코드로 보면 더 이해하기 쉬운 문제이다.
N = int(input()) # 설탕 무게를 입력 받는다.
result = 0 # 봉지 총 개수 초기화
if N % 5 == 0: # N이 5kg으로 나누어 떨어지는 경우
result = N // 5
print(result)
else: # N이 5kg으로 나누어 떨어지지 않는 경우
while N > 0:
N -= 3
result += 1 # 3kg 봉지의 개수 +1
if N % 5 == 0:
result += N // 5 # 3kg 봉지의 개수 + 5kg 봉지의 개수
print(result)
break
elif N < 0: # N을 3과 5로 나눌 수 없는 경우
print(-1)