[코딩테스트/ 백준 알고리즘] 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 sugar[5001] = {0};

int DP(int input) {

    // 중복 계산을 막기 위함
    if(sugar[input] != 0) {
        return sugar[input];
    }

    // input이 3 또는 5일 경우 0 반환
    if(input == 0){
        return 0;
    }

    // input이 음수일 경우 의미 없는 큰 수 반환
    else if (input < 0) {
        return 9999;
    }

    // input이 1, 2, 4일 경우 의미 없는 큰 수 반환
    else if (input == 1 || input == 2 || input == 4) {
        return 9999;
    }


    else {
        /* 점화식 참고*/
        sugar[input] = min(DP(input - 5), DP(input - 3)) + 1;
        return sugar[input];
    }
}

int main() {
    int input = 0;

    cin >> input;
    DP(input); //DP 함수 호출

    //sugar[input]이 0과 10000이라는 것은 해당 입력 값을 나타낼 수 없다는 의미 이므로 -1로 출력
    cout << ((sugar[input] == 0 || sugar[input] == 10000) ? -1 : sugar[input]) ;

    return 0;
}

 

---

총평

"백준 1463번 : 1로 만들기" 문제를 풀다가 다이나믹 프로그래밍에 대해 공부해야겠다고 생각해서 다시 풀어본 문제다.

1년 전에 풀었을 때는 그리디 알고리즘을 통해 해결했지만 이번에는  다이나믹 프로그래밍을 통해 해결해봤다.

다이나믹 프로그래밍은 재귀를 통한 탑다운 방식과 반복문을 통핸 바텀업 방식이 있다.

이 글에서는 탑다운 방식을 통해 해결했고, 바텀업 방식을 통해 해결한 풀이도 올릴 생각이다.

조만간 다이나믹 프로그래밍에 대해 정리하는 글을 써봐야겠다.