[백준(BOJ)] 2839번 설탕 배달 C++(다이나믹 프로그래밍)

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

2839번: 설탕 배달

 

 

어떤 문제인가?

설탕을 n킬로그램을 배달해야 한다.

설탕은 3kg, 5kg 봉지로만 존재해 이 두 가지 종류의 봉지만 사용하여 배달을 해야 한다.

이때, 배달에 필요한 최소 봉지의 개수를 출력하면 된다.

 

이 문제는 예전에 그리디 알고리즘을 공부할 때 풀었던 문제이다.

지금은 다이내믹 프로그래밍을 공부 중인데 문제가 있어서 이번엔 dp로 풀어보았다.

https://codegarden-farmjun.tistory.com/10

[백준(BOJ)] 2839번 설탕배달 C++ (그리디 알고리즘)

 

 

접근 방법

일단 dp로 문제에 접근하기에 점화식을 세워야 한다.

 

int dp[5001];

n이 5000까지 입력될 수 있으므로 크기 5001의 배열을 선언해준다.

 

 

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

dp [ i ] = x는

i Kg을 운반하는데 필요한 봉지수가 x 개라는 뜻이다.

 

3kg을 운반하는데 필요한 봉지수는 1개

5kg을 운반하는데 필요한 봉지수는 1개

라는 뜻이다.

 

fill(dp, dp + 5001, 10000);
for (int i = 6; i <= n; i++) {
    dp[i] = min(dp[i - 3], dp[i - 5]) + 1;
}

이제 6부터 n까지 반복을 통해 dp 값을 계산할 것이다.

이때, 최대한 적은 봉지를 계산하는 것이기 때문에

dp [ i ] 값을 min함수를 써줘서 i -3, i - 5번째 인덱스를 비교하여 더 작은 값에 1을 더해준다.

 

여기서 중요한 것은 작은 값을 비교하는 것이기 때문에 

처음에 무게들(인덱스의 값)을 모두 10000으로 해주어 min함수에서 비교 시 영향이 가지 않도록 해준다.

 

6이 입력됐다면

dp [ 6 ] = min( dp [ 3 ] + dp [ 1 ]) +1이 된다.

따라서 dp [ 6 ] = 2

 

이렇게 dp값들을 미리 알고 있다면 나중에 또 계산할 필요 없이 바로 사용할 수 있게 된다.

 

if (dp[n] > 10000) {
    cout << -1;
} else {
    cout << dp[n];
}

 

10000보다 크다면 배달할 수 없다는 뜻이니까 -1을 출력

그렇지 않다면 n번째 인덱스 값을 출력해주면 끝이다!

 

무엇이 어려웠는가?

그리디로 풀 때의 방식만 생각이 나서 dp 쪽으로의 생각이 더뎠다.

그래도 패드에 천천히 쓰다보니 규칙이 보였고 점화식을 찾아 이를 그대로 구현만 하면 됬었다.

 

 

배운 점

같은 문제라도 풀이 방법이 완전히 다를 수도 있다.

문제를 풀었다고 끝이 아니라 다른 방식으로도 풀 수 있는지 확인해보자.