[python] 백준 2839 - 설탕 배달

출처 : 백준, https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 

먼저, 생각해야 할 부분

 

1. 딱히 없지만, 알아두면 좋을 것이 이 문제는 2가지 방식으로 풀 수 있다.

     문제를 풀고 자신이 문제를 푼 방식과 다른 방식으로도 한 번 더 풀어보자.

 

---

 

풀이1 : Greedy

 

n = int(input())

a = n // 5

while True:
  if a < 0:
    print(-1)
    break
    
  new_N = n - a * 5
  if new_N % 3 == 0:
    print(a + new_N // 3)
    break

  a -= 1

 

항상 나는 그리디 방식의 풀이가 먼저 떠오르는 편인데,

DP 카테고리에 있던 문제라 이게 아닌데.....이러면서 풀었다.

둘 다 되더라궁 ㅎㅎ

 

최소가 되려면 용량이 큰 5kg의 개수가 많으면 되므로, 

5kg의 개수를 최대로 한 상태에서 개수를 1씩 줄여가며 3으로 나누어 떨어질 때 출력해주었다.

5kg의 개수가 음수가 되면 5키로와 3키로로 나뉠 수 없는 무게이므로 -1을 출력해주었다.

 

풀이2 : DP

 

n = int(input())

a = n // 5

while True:
  if a < 0:
    print(-1)
    break
    
  new_N = n - a * 5
  if new_N % 3 == 0:
    print(a + new_N // 3)
    break

  a -= 1

 

나는 DP 풀이법을 떠올리는 것을 잘 못하는 편인데, 변명하자면 내 코테는 아직 구현 원툴이다......

결국 다른 분의 블로그에서 핵심 아이디어 한 줄을 참고했다.

 

"(i-3)kg과 (i-5)kg의 봉지 개수 중 최소를 고르면 된다."

 

와, 엄청난 아이디어야! 즉, min(dp[i-5], dp[i-3]) + 1이라는 점화식을 세울 수 있다.

이 아이디어를 바탕으로 문제를 해결하기 위한 풀이를 생각해보면,

가로축에는 0부터 n kg까지 나열하고, 세로축으로는 3kg을 골랐을 때와 5kg을 골랐을 때를 구분한다.

 

	0	1	2	3	4	5	6	7	8
i-3 kg	n	n	n	1	n	n	2	n+1	2
i-5 kg	n	n	n	n	n	1	n+1	n+1	2
min(i-3, i-5)	n	n	n	1	n	1	2	n+1	2

 

n을 3이나 5로 나누어 담게 되므로 n개가 될 수는 없다. 이를 이용해 일단 n으로 초기화를 진행했다.

그리고 dp[3]을 1로, dp[5]를 1로 세팅하고 진행한다.

0~5까지는 미리 세팅해두고, 차례로 계산하며 min 값을 업데이트한다.

이 때, n보다 크거나 같다면 만들 수 없는 값이므로 -1을 return하면 된다.

---

시간 복잡도

DP의 경우는 O(3n)

Greedy의 경우는 O(n//5)......이라고 표현할 수 있으려나?

결국에 O(n)이긴 한데 Greedy가 반복 횟수가 적으므로 걸리는 시간이 짧다고 추측된다.

 

알게 된 점

 

DP 풀이를 떠올리는데 도움이 되는 방법

 

바로 1단계 전을 떠올린다.

즉, 3kg, 5kg이 있다면 3kg 전....5kg 전을 떠올린다.

 

고찰

 

-

 

Github

백준 2839 - 설탕 배달

 

Reference

[알고리즘] 백준 BOJ 2839번 설탕 배달 - 두 가지 해설(C, C++)