백준 2839) 설탕배달

 

접근방식

- 최소 봉지수를 구하기 위해서는 3보단 5로 많이 나누어야한다.

  따라서 킬로그램에서 3씩 마이너스를 해주어 5로 나누어 떨어지는지 확인하였다.

  3을 계속 빼주어 n이 마이너스가 되어버리는 경우는 -1을 출력해주었다.

 

 

 

n = int(input())

cnt =0

while n >0:

    if n%5 == 0:

        cnt += n//5

        break

    n -= 3

    cnt +=1

if n >=0:

    print(cnt)

else:

    print(-1)

 

 

풀이 중에 dp 방식으로도 풀 수 있을 거 같아서 코딩을 해보았다.

 

-------------

n = int(input())

d = [10001] *(n+1)

cnt = 0

d[0] = 0

d[3] = 1

for i in range(5,n+1):

    d[i] = min(d[i-3],d[i-5]) + 1

if d[n] == 10001:

    print(-1)

else:

    print(d[n])