[코딩테스트/ 백준 알고리즘] BOJ.2839 : 설탕배달 (바텀업) (C++ 풀이)

문제

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

---

풀이

자료구조

 - int sugar[5001] : DP 테이블

 - int input : 입력 값

 

알고리즘

- 다이나믹 프로그래밍

- 반복을 통한  바텀업 방식 사용

- 점화식 : sugar[input] = min(DP(input - 5), DP(input - 3)) + 1

 

코드

-  두 수 중에 최솟값을 구하는 min() 함수를 구현하기 귀찮다면 C++에서 <algorithm> 라이브러리를 추가하면 된다.

코드 

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

int main() {
    int sugar[5001] = {0};
    int input = 0;
    cin >> input;

    // 초기 테이블 세팅
    sugar[3] = sugar[5] = 1;
    sugar[1] = sugar[2] = sugar[4] = 9999;

    // 1부터 5까지는 테이블이 이미 채워져 있기 때문에 6부터 input까지 테이블을 순서대로 채움
    for(int i = 6; i <= input; i++) {
        sugar[i] = min(sugar[i - 3], sugar[i - 5]) + 1;
    }
    cout << ((sugar[input] == 0 || sugar[input] >= 9999) ? -1 : sugar[input]) ;

    return 0;

}

 

---

총평

탑다운 방식으로 한번 풀어봐서 그런지 바텀업으로 바꾸기 쉬웠고, 코드도 더 예쁘게 나왔다.

나도 진짜 자세히 설명도 쓰고 그림도 그리고 싶지만 그럴 재주가 없다.

조만간 다이나믹 프로그래밍에 대해 내가 아는한에서 최대한 자세히 글을 써보도록 하겠다.