[백준] 2839 설탕 배달

Posted on | In

정말정말 오랜만에 백준 문제를 가지고 왔다! 설탕 배달이라는 문제인데, dp로 풀 수 있는 문제라고 해서 가져왔다. 옛날에 틀린 문제라 무작정 어렵다는 생각을 가지고 도전하지 않았던 문제인데, 왠걸 지금 푸니까 한번만에 맞췄다! 실력이 조금씩 조금씩 늘고 있는 것 같아 기분이 좋다.😊

문제 설명

링크 설탕 배달을 하는 문제이다. 설탕 그람 수가 n으로 주어지면, n그램을 3그램 봉지들과 5그램 봉지들로 만들면 된다. 이때, 총 봉지 수가 최소로 하는 문제이다.!

문제 풀이

dp라는 걸 알고 보아서 그런지는 모르겠지만 간단하다!

  • dp[n] : n그램을 만드는 데 필요한 봉지 수

채울 수 없는 봉지들은 INTMAX로 두고, (나는 그냥 엄청 큰 수로 두었다) for문을 돌면서 dp를 갱신해주면 된다. 이때, n번째 그램은 n-3그램을 만드는데 필요한 봉지 수에서 3그램 봉지를 하나 더하거나, n-5그램을 만드는 필요한 봉지 수에서 5그램 봉지를 하나 더하면 구할 수 있다. 봉지 수가 최소가 되야 하므로, 둘 중 더 봉지 수가 작은 걸 선택하면 된다! 내가 채울 수 없는 봉지들을 INTMAX로 둔 이유는, 채울 수 없는 봉지들을 이용해서 dp값이 갱신 될때, INTMAX값 이상의 값은 무시될 수 있기 때문이다. 채울 수 없는 k그램을 이용해 k+3/k+5그램을 갱신하게 되면, 더 작은 봉지 수를 선택하므로 k그램이 무시되거나, 갱신하는 그램 또한 만들 수 없는 그램이 되어 INTMAX보다 더 큰 값으로 갱신이 된다. 결국 INTMAX이상의 값들은 사용할 수 없는 값으로 보고, -1을 출력해 주면 된다. 아래는 코드이다.!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>

int dp[5001];

int main(){
    int n;
    scanf("%d", &n);

    dp[0]=100000001;
    dp[1]=100000001;
    dp[2]=100000001;
    dp[3]=1;
    dp[4]=100000001;
    dp[5]=1;

    for(int i=6;i<=n;i++){
        dp[i]=(dp[i-3]<dp[i-5])?dp[i-3]+1:dp[i-5]+1;

        //printf("%d: %d vs %d => %d\n", i, dp[i-3], dp[i-5], dp[i]);
    }

    printf("%d\n", (dp[n]>=100000001)?-1:dp[n]);

}