백준 2839 설탕배달

문제

---

 

정답

n = int(input())

if n%5==0:
    print(n//5)
else:
    cnt=0
    while n>0:
        n-=3
        cnt+=1
        if n % 5 ==0:
            cnt+= (n//5)
            print(cnt)
            break
        elif n==0:
            print(cnt)
            break
        elif n==1 or n==2:
            print(-1)
            break

---

깨달은 점

먼저 경우의 수를 생각해야한다. 

 

1. n이 5로 나눠질경우 (if문)

2. n이 5와 3으로 나눠질 경우
    (3kg씩 빼면서 5로 나눠질 경우에는 5로 나눈 값 더해서 출력)

3. 3으로 나눠질 경우

   -> 3kg씩 빼면서 나머지가 1과 2kg일때 나눌 수 없는 값 -1 출력

4. 5와 3으로 나눠지지 않을 경우

   -> -1 출력

 

이런식으로 풀었는데 코드가 깔끔하지 않다.

그리디 알고리즘을 생각은 했는데 제대로 풀지못했다.

 

 

---

다른 풀이법

 

다이나믹프로그래밍 풀이법

N = int(input())
dp = [0] * max(6, N+1)

dp[3], dp[5] = 1, 1

for n in range(6, N+1):
    # 1
    if dp[n-3]:
        dp[n] = dp[n-3] + 1
	
    # 2
    if dp[n-5]:
        if dp[n-3]:
            dp[n] = min(dp[n], dp[n-5] + 1)
        else:
            dp[n] = dp[n-5] + 1

print(dp[N]) if dp[N] else print(-1)


//출처: https://corin-e.tistory.com/entry/백준-2839-설탕-배달-파이썬 [🪨 🪨 🪨:티스토리]

 

 

 

 

그리디 알고리즘 풀이법 🌟🌟🌟

n = int(input())

cnt = 0
while n >= 0:
    if n % 5 == 0:
        cnt += (n // 5)
        print(cnt)
        break
    n -= 3
    cnt += 1
else:
	print(-1)

 

+  While문 else: 

         루프가 break 등에 의해서가 아닌 자연적으로 끝나는 경우 실행