Baekjoon 2839번 설탕 배달

풀이

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

걸린 시간

00 : 19 : 58

풀이

Python3

if __name__ == "__main__":
    N = int(input())    

    result = []

    # 1. 5로 나눈 몫을 0까지 하나씩 줄여 나간다.
    quotient = N // 5 
    while quotient >= 0 : 
        tmp = []
        tmp.append(quotient)
        remainder = N - 5 * quotient
        # 2. 나머지를 3으로 나누어 떨어지는지 확인한다.
        if remainder % 3 == 0:
            tmp.append(remainder//3)    
            result.append(tmp)
        quotient -= 1

    # 3. 5로 나눈 몫이 최대일 때의 값을 결과값으로 한다.
    result.sort()

    if len(result) != 0:
        print(sum(result[-1]))
    else:
        print(-1)

다른 풀이

C++

#include <stdio.h>
#include <iostream>
#include <string.h> // memset
using namespace std;

int cache[5001];

int dp(int n){
    // 기저 사례
    if(n == 0)
        return 0;
    if(n < 3)
        return -1;
    // 메모이제이션
    int& ret = cache[n];
    if(ret != -1)
        return ret;
    // 재귀 호출
    int big = -1;
    int small = -1;
    if(n-5 >= 0)
        big = dp(n-5);
    if(n-3 >= 0)
        small = dp(n-3);
    int tmp = min(big, small);
    // 정확하게 만들지 못하는 경우가 있으면
    if(tmp == -1)
        if(big == -1 && small != -1)
            return ret = small+1;
        else if(big != -1 && small == -1)
            return ret = big+1;
        else
            return ret = -1;
    else
        return ret = tmp+1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << dp(N) << "\n";
    return 0;
}

종만북을 보고 이전에 풀었던 그리디 알고리즘 문제를 다시 풀어보려 했으나, 탐욕법 개념을 잘못 이해하고 접근한 탓에 결국 dp로 풀이했다. 일반적인 구현 문제인 줄 알고 작성했던 첫 풀이가 탐욕적 알고리즘이다.

탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다고 한다. 문제를 읽고 이해한 뒤 계획을 세우는 단계에서 제일 처음으로 탐욕적 알고리즘을 적용할 수 있는가를 먼저 생각해 보는것이 좋을 것 같다.