[그리디/백준] 2839번: 설탕 배달(2차)

-문제:https://www.acmicpc.net/problem/2839

 

처음에는 5를 기준으로 하고, 나머지는 3키로 봉지로 충당하면되겠지 생각했는데, 정확하게 n키로를 5와 3으로 맞춰야 정답이다

5를 기준으로 생각하는 것 맞지만, 18 같은 경우는 3*6도 되고, 15+3도 되기 때문에 이거를 어떻게 해야할지 몰랐다 

나름 dp로 풀어본다고 했는데 틀린 답이 나왔다 

 

-정답 풀이:

while문을 돌리면서 5의 배수이면 그대로 계산하고, 아닌 경우는 3을 감소시키면서 지켜본다 

while문에서 출력이 되지 않으면 n<0인 상황이 되어 while문을 나오는데, 그 경우에는 -1을 출력해주면 된다 

n=int(input())
dp=[0]*5001
dp[3],dp[5]=1,1
bag=0
while n>=0:
    if n%5==0:
        bag+=n//5
        print(bag)
        break
    else:
        n-=3
        bag+=1
else:
    print(-1)

 

-틀린 풀이: 

n=int(input())
dp=[0]*5001
dp[3],dp[5]=1,1
bag=0
for i in range(6,n+1):
    if dp[i-5]!=0:
        bag= 1+dp[i-5]
    elif i%3==0:
        dp[i]=i//3
    else:
        print(-1)
        break
print(dp[n])