[C++] 백준 2839번 : 설탕 배달 (B1)

#문제

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

#풀이

이 문제는 dp를 통해 해결하는 문제이다. Nkg 최적화 문제를 N-3kg 최적화 문제와 N-5kg 최적화 문제를 통해 답을 도출하는 optimal substructure로 구현했다. 기본적인 구현은 쉬웠지만, 정확하게 N킬로그램을 만들 수 없을 때 -1을 출력하게 만드는 것에서 약간 고민을 해야했다. 문제를 해결한 뒤 다른 분의 dp풀이(링크) 코드를 봤는데, 훨씬 깔끔했다. 나는 3을 빼고 5를 빼는 과정에서 필요한 부분만 계산했지만, 다른 분은 그저 N까지 순서대로 모두 계산했다. 시간복잡도에 큰 차이가 없으므로 for문으로 N까지 순서대로 모든 수에 대해 계산하는 것이 더 좋은 것 같다. 그리고 초기의 vector에 모두 아주 큰 값을 넣어주어 -1출력부분을 처리한 점도 훨씬 깔끔했다. 다른 분의 코드를 보며 추가로 C++ STL Vector(링크)에 대해서도 학습했다.

 

#소스 코드

#include<iostream>
#include<algorithm>
 
using namespace std;
int arr[5005];//처음에 모두 0으로 초기화됨
 
int opti(int num) {
    if (arr[num] == -1)
        return -2;
    else if (arr[num] > 0)
        return arr[num];
    else {
        int n1 = opti(num - 3) + 1;
        int n2 = opti(num - 5) + 1;
 
        if (n1 == -1 && n2 == -1)
            return -2;
        else if (n1 == -1 || n2 == -1) {
            arr[num] = max(n1, n2);
            return arr[num];
        }
        else {
            arr[num] = min(n1, n2);
            return arr[num];
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    arr[0] = -1; arr[1] = -1; arr[2] = -1;
    arr[3] = 1; arr[4] = -1; arr[5] = 1;
 
    int N;
    cin >> N;
    int result = -1;
 
    if (N <= 5)
        result = arr[N];
    else {
        int n1 = opti(N - 3) + 1;
        int n2 = opti(N - 5) + 1;
        if (n1 == -1 || n2 == -1)
            result = max(n1, n2);
        else
            result = min(n1, n2);
    }
    cout << result << "\n";
}