백준 2839번 - 설탕배달 문제 C++ [그리디 알고리즘/다이나믹 프로그래밍]

📍 백준 2839번 - 설탕배달 문제 C++ [그리디 알고리즘/다이나믹 프로그래밍]

---

🧩문제 요약

<그리디 알고리즘/다이나믹 프로그래밍>

3kg, 5kg의 설탕 봉지가 있다. 

n이 주어졌을 때 n을 만족하기 위해서 위의 설탕 봉지를 최소한으로 하는 봉지갯수를 return 하라. 

n에 딱맞춰야함. 만약 그럴수 없을 경우 -1을 return 

---

🧾내가 작성한 초기 코드 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n, cnt, answer, i=1, a=1001, b=1001, c=1001, d=1001;
    cin >> n ;

    if(n%5==0){
        a=n/5;
    }
    if(n%3==0){
        b = n/3;
    }
    
    for(i=1;n-5*i>=0;i++){
        if( (n-(5*i))%3 ==0){
            c = i+(n-(5*i))/3;
        }
    }
    for(i=1;n-3*i >=0;i++){
        if( (n-(3*i))%5 ==0){
            d = i+(n-(3*i))/5;
        }
    }

    answer = min(min(a,b),min(c,d));
    if(answer >1000 ){
        cout << -1 << "\n";
    }else{
        cout << answer << "\n";
    }
    

}

---

👍이 문제에서 배운점

처음에는 이 문제를 그리디와 다이나믹 프로그래밍을 사용할 생각을 못하고 그냥 무작정 코드 작성에 진입했더니 당연히 구현이 안되고 계속 오답만 받았다. 하지만 이제는 전형적인 DP/그리디 문제라는 것을 알 수 있다. 

위의 코드도 로직은 맞지만 놓치고 있는 문제들이 몇개 있다. 

😕 문제점 1. 

초기값 설정이 잘못됨

위의 코드에서는 a, b, c, d = 1001로 설정했는데,  여기서 n은 5000까지 가능하다. 그래서 사실은 비효율적인다. 

 

✅1e9를 사용 

더 좋은 방법으로는 a, b, c, d = 1e9로 하는 것이 더 안전하다. 

 

 백준에서 n은 최대 5000으로 잡혀 있기 때문에 1001을 충분히 넘어설 수 있다. 

예를 들어, n = 5000

• a: n % 5 == 0 → ✅ a = 5000 / 5 = 1000
• b: n % 3 == 0 → n % 3 == 2 → b = 1001
• c, d loop: i=1 ~ i=999 loop 돎
  • c: (5000 - 5 * i) % 3 == 0 이면 update
  • d: (5000 - 3 * i) % 5 == 0 이면 update

→ 여기서 최소 answer 이 1000 이 될 수 있는데, 아래의 로직으로 -1이 출력되버린다. 

if (answer > 1000) cout << -1;

 

😕 문제점 2. 

a, b가 1001로 유지될 수 있음

예를 들어 n = 4 인 경우:

• 4는 5로 안 나누어짐 → a = 1001 (변하지 않음)
• 4는 3으로 안 나누어짐 → b = 1001 (변하지 않음)

그래서 초기값을 최소값 비교할 때 영향을 준다.
근데 이건 answer 비교할 때 1000 초과일 경우 -1 처리하는 것으로 커버는 하고 있지만 좋은 코드는 아니다. 

 

😕 문제점 3.

이중 루프 안 쓴 부분  

사실 c와 d는 이중 루프 없이도 구할 수 있는데,  

5*i 쓰는 경우 (c)와 3*i 쓰는 경우 (d)를 따로 계산했다.

 

문제는, c 와 d 가 사실상 같은 범위를 커버하는데, 일부 조합을 놓치게 된다.

예를 들어 n = 7일때, 

• 7은 5로만 안 나눠짐 → a = 1001
• 7은 3으로도 안 나눠짐 → b = 1001
• c loop:
  • i = 1 → (7 - 5) = 2 → 2 % 3 != 0 → 통과
  • i = 2 → (7 - 10) = -3 → break (사실 i < n/5로 돌아가서 끝)
• d loop:
  • i = 1 → (7 - 3) = 4 → 4 % 5 != 0 → 통과
  • i = 2 → (7 - 6) = 1 → 1 % 5 != 0 → 통과

👉 결국 c, d 둘 다 못 찾음 → answer = min(1001, 1001, 1001, 1001) → 1001 → -1 출력

여기까지는 잘 작동한다. 

 

하지만 코드가 비효율적이고 중복계산을 포함하고 있다는 것을 알 수 있다. 

---

 

🧾 완성된 코드 

#include <iostream>
using namespace std; 

int dCnt[5001];

int Dp(int n){
    dCnt[3]= 1;
    dCnt[5] = 1;
    for(int i=6; i<=n; i++){
        if(dCnt[i-3]){
            dCnt[i] = dCnt[i-3] + 1;
        }
        if(dCnt[i-5]){
            dCnt[i] = dCnt[i]? min(dCnt[i], dCnt[i-5]+1) : dCnt[i-5]+1;
        }
    }
    return (dCnt[n]==0 ? -1 : dCnt[n] );
}

int Greedy(int n){
    int answer=0 ; 
    while(n>=0){
        if(n%5 == 0){
            answer += n/5;
            return answer ;  
        }
        n -=3 ; 
        answer++;
    }
    return -1; 
}

int main(){
    int n, i,answer ; 
    cin >> n ;
    // answer = Dp(n);
    answer = Greedy(n);
    cout << answer << "\n" ;
    return 0; 
}

완성된 코드는 그리디 알고리즘과 다이나믹 프로그래밍으로 해결한것이다. 

 

✅ DP

먼저 DP방식을 살펴보면 n이 주어졌다고 할 때 n의 최솟값은 (n-3)kg의 최소봉지+1, (n-5)kg의 최소봉지+1이다. 

그럼 이것을 이용해 처음에 초기값 3kg일때 한봉지, 5kg일때 한봉지를 설정하고 6kg일 때부터 n-3, n-5로 연산을 하면 값을 어렵지 않게 구할 수 있다. 

 

이 문제에서 알 수 있었던 점은 배열은 전역변수로 선언하면 자동으로 초기값을 0으로 설정한다는 것이였다. 

 

✅Greedy

다음 그리디 방식은 일단 5kg으로 채울 수 있으면 채우는 것이 무조건 이득이라는 것이다. 

최소 갯수를 만족하려면 5kg을 많이 쓸수록 최소에 가까워지기 때문이다. 

때문에 n이 5로 나누어지는지를 꾸준히 확인하는 것이 핵심이다.

 

만약, n으로 나눌 수 없다면 n에서는 3을 빼보고 n-3이 5로 나누어지는를 확인하며 3kg을 최소화 하며 5kg을 제일 많이 소비할 수 있는 방향으로 구현할 수 있다. 

 

 

---

 

초기의 코드도 a=b=c=d를 1e9로 변환하고 마지막 조건을 변경하면 정답일 수 있지만, 코드가 다소 복잡하고 안전성이 보장된지 않는다는 문제점이 있었다. 

 

코드를 조금더 깔끔하고 연산량을 줄이고 안전성을 지킬 수 있는 방식으로 작성하는 연습이 필요한것 같다.