백준 - 설탕 배달(Python)

백준 - 설탕 배달(Python)

 

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

이 문제를 접근할 때 맨처음에 떠오른 생각은 dp를 이용해서 풀어야겠다고 생각했다. dp의 인덱스는 0이 될 수 있는 최소한의 연산 횟수이다.

 

 

dp[3] = 1, dp[5] =1로 두고 (3과 5일때 바로 그 두 값을 뺄 수 있기 때문에) range(6, 입력값)으로 for문을 돌렸다.

 

for문의 내용은 3으로 뺀값이 최대값이 아닐때(값이 있을 때) 그 수에 +1(연산 횟수)를 해주었다.

 

그렇게 i-3과 i-5를 통한 d[i]의 값 중에 최소값을 d[i]로 설정했다.

 

 

소스 코드로 보는 게 더 간편할 것이다.

 

n = int(input())

dp = [5001]*5001

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

for i in range(6,n+1):
  if dp[i-3] != 5001:
    dp[i] = dp[i-3]+1
  if dp[i-5] != 5001:
    dp[i] = min(dp[i], dp[i-5]+1)
    
if dp[n] == 5000:
  print(-1)
else :
  print(dp[n])

다른 블로그를 확인해보았더니 전부 필자방식과 다른 방법으로 풀이하고 있었다.

(필자가 많이 부족한 탓이다)

 

통용적으로 쓰고 있는 풀이 또한 살펴보자.

이 풀이는 위의 코드보다 더욱더 깔끔하고 직관적이다.

1. 5로 나눌 수 있으면 나눈다. 

2. 5로 못나누면 입력값에서 3을 빼고 count를 올린다. 

3. 1,2번을 반복하는데 만약 5로 못나누고 계속 3을 빼면서 입력값이 0보다 작아진다면 -1를 리턴해준다.

 

이 아이디어는 "5로 나눌 수 있으면 무조건 나눠라"가 핵심 아이디어이다.

 

아래 소스 코드를 확인해보자.

 

n = int(input())

count =0

while True:
  if n%5==0:
    count = count + n//5
    print(box)
    break
  else :
    n = n-3
    count +=1
  if n<0:
    print(-1)
    break