백준 2839 - 설탕 배달 [C/C++]

2839번: 설탕 배달 (acmicpc.net)

2839번: 설탕 배달

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

대표적인 Dynamic Programming 문제라고 할 수 있을 것 같다.

 

이전의 값들을 참조해서 현재의 값들을 update 하고, 그게 다음의 값까지 이어지는 프로그래밍 방식의 아주 기초적인 문제라고 생각했고, 그 알고리즘을 그대로 사용해서 풀었다.

 

우선 내가 생각한 알고리즘은 다음과 같다.

 

1. 1~5000까지의 input이 들어갈 수 있으니, 그거에 맞는 int[5001] 배열을 만든다. (0으로 초기화)

2. 1부터 5000까지, 3kg와 5kg의 설탕의 최소 배합으로 만들 수 있는 숫자를 채워넣는다.

3. 이 때, N 킬로그램의 무게를 채우고 싶다면, 다음의 경우의 수가 있다.

• N 킬로그램이 3으로 나누어 떨어져서, 그냥 3kg 짜리로 다 채우면 되는 경우의 수
• N 킬로그램이 5로 나누어 떨어져서, 그냥 5kg 짜리로 다 채우면 되는 경우의 수
• 둘 다 나누어 떨어지지는 않는 경우
  • N-3 킬로그램이 채워진 방식 + 1 (3kg를 채우는 방식)
  • N-5 킬로그램이 채워진 방식 + 1 (5kg를 채우는 방식)

다음의 경우의 수 중 가장 minimal 한 값이 그 배열의 인덱스의 Value 값이 될 것이다.

 

아래는 그 경우의 수 중 가장 min 값을 구해내는 C++ 코드이다.

#include <iostream>

using namespace std;
int anslist[5001] = {0, };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int num;
    cin >> num;
    cin.ignore();
    anslist[3] = 1;
    anslist[4] = 0;
    for (int i = 5; i<5001; i++){
        if (anslist[i-3] != 0){
            anslist[i] = (i%3==0) ? min(anslist[i-3] + 1, i/3) : anslist[i-3] + 1;
            if (anslist[i-5] != 0) {
                anslist[i] = (i%5==0) ? min(anslist[i-5] + 1, i/5) : min(anslist[i-5] + 1, anslist[i]);
            }
        }
        else {
            anslist[i] = (i%3==0) ? i/3 : 0;
            anslist[i] = (i%5==0) ? max(i/5, anslist[i]) : 0;
        }
    }
    int a = anslist[num] == 0 ? -1 : anslist[num];

    cout << a << '\n';

    return 0;
}