beaekjoon 2839

백준 2839번

백준 2839번 문제

문제 설명

N kg의 설탕을 5 kg, 3 kg 봉지에 포장을 해야된다. 최소 봉지 개수를 출력하는 문제이다. 두 종류의 봉지로 포장이 불가능할 경우 -1 을 출력한다.

입력	5 kg 봉지 개수	3 kg 봉지 개수	출력
18	5	1	4
4	0	0	-1
6	0	2	2
9	0	3	3
11	1	2	3

Greedy

방법 1

설탕이 3 kg 봉지를 이용하지 않고 5 kg 봉지만 이용해서 포장을 할 수 있으면 가장 적은 양의 봉지를 사용하는 것 입니다. 즉 이 방법은 N 이 5로 나누어 떨어질때까지 계속 3을 빼주면 최소 봉지의 양을 구하는 방법입니다.

greedy를 이용한 코드

#include<stdio.h>

int main()
{
    int total, result = 0;
    scanf("%d",&total); // N kg 의 설탕 입력 받기

    while(total >0)
    {
        if (total % 5 == 0)
        {
            result += total / 5;
            total = 0; 
            // 현제 설탕양이 5로 나누어 떨어지면 5 kg 봉지로 전체 포장
        }
        else
        {
            total -= 3;
            result ++;
            // 5로 나누어 떨어지지 않으면 3 kg 봉지로 한번 포장
        }
    } // 0 이하가 될때 까지 반복
    if (total == 0)
    {
        printf("%d",result); // 정확하게 포장 하면 봉지의 양을 출력
    }
    else
    {
        printf("-1"); // 정확하게 포장 실패할때 -1 출력
    }

    return 0;
}

DP

현제 i kg의 설탕을 포장 할 경우, (i-3) kg 의 설탕을 포장한 봉지 개수와 (i-5) kg 의 설탕을 포장한 봉지 개수를 비교해 더 작은거에 1을 더하면 최소 봉지 양을 구할 수 있습니다.

dp[i] = ((dp[i-3] < dp[i-5]) ? (dp[i-3] + 1) : (dp[i-5] + 1))

[요기서 A ? B : C 는 A 가 참일 경우 B를, 거짓일 경우 C를 실핼 하는 거 입니다.]

하지만 정확하게 포장을 못하면 -1을 출력 해야됩니다. 그러기 위해서는 memset 함수를 이용해 dp 리스트를 -1로 다 초기화 해줍니다

memset(dp,-1,(N +1)*sizeof(int)); // 리스트의 크기는 N +1

dp를 이용한 코드

#include <stdio.h>
#include <string.h> // memset 함수를 아용하기 위함
int main()
{
    int total;
    scanf("%d",&total);

    int dp[total+1]; // N 만큼의 양을 계산하기 위해 dp 리스트 생성
    memset(dp,-1,(total +1)*sizeof(int)); // dp에 있는 모든 값을 -1로 초기화
    dp[3] = 1;
    dp[5] = 1;
    // 5 kg 보다 작을 때는 3 kg, 5 kg를 제외하고는 포장이 불가능 하니 6키로부터 for문을 이용해 계산
    for(int i = 6;i<=total;i++)
    {
        if(dp[i-3] != -1)
        {
            dp[i] = dp[i-3] +1;
            //  i -3 kg 포장 값이 존재 하면 dp[i-3] 값에서 +1
        }
        if(dp[i-5] !=  -1)
        {
            dp[i] = (dp[i] != -1) ? ((dp[i] < dp[i-5]+1) ? dp[i] : dp[i-5]+1)  : dp[i-5] +1; 
            // 이미 첫번째 if문을 통해 값이 있을 경우 (i - 3 kg 가 존재 할 경우) dp[i-3]이랑 dpv[i-5] 중 작은 값에 +1
                // 그게 아니면 dp[i-5]에 +1 
        }
    }

    printf("%d",dp[total]);

    return 0;
}

이상 두가지 풀이방식으로 문제를 풀어봤는데, dp 와 greedy를 둘 다 사용 할 수 있어 재밌는 문제였습니다.