백준 2839 설탕 배달 Python

🐸 문제 정보

2839번: 설탕 배달

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

17.15m

 

📝 풀이

아주 오래전에.. 2년 전에 풀었던 문제인 것 같다.

알고리즘이 열려있어서 우연찮게 DP라는 걸 봐버렸는데ㅠ

처음에 그리디로 풀려다가 DP로 풀어야하나?! 하고 괜히 고민하느라 더 오래걸렸다.

그냥 그리디로 풀면 쉽게 풀 수 있는 문제였다.

1. 남은 설탕 무게가 5의 배수라면, 5로 나눈 몫만큼 개수 더해주고 반복문 탈출
2. 기본적으로 남은 무게에서 3키로씩 빼주면서 반복
3. 반복문 탈출 후, 남은 무게가 0키로라면 반복 과정에서 센 개수 출력
   • 아니라면, -1 출력

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
res = 0
while 0 < n:
    if n % 5 == 0:
        res += n // 5
        n %= 5
        break
    n -= 3
    res += 1

if n == 0:
    print(res)
else:
    print(-1)