(백준) 2839 설탕 배달 c++ 그리디 알고리즘

해당 문제는 그리디 알고리즘 ( 탐욕법 )으로 풀 수 있다. 간단히 해당 알고리즘을 적용하여 풀이 법을 그림으로 살펴보자면

일단 N이 11이라고 가졍했을 때, 5로 먼저 뺄 수 있는지 확인 후 5로 뺄 수 있으면 빼준다.

이후 (11-5)가 다시 5로 먼저 뺄 수 있는지 확인하고 뺄 수 있다면, 또 빼준다.

(11-5-5)가 다시 5로 먼저 뺄 수 있는지 살펴본다.
뺄 수 없으니 이제 3으로 뺄 수 있는지 살펴본다.
뺄 수 없으니, 다시 (11-5)로 돌아가서 3으로 뺄 수 있는지 살펴본다.

뺄 수 있으니 (11-5-3)이 5로 뺄 수 있는지 살펴본다.
뺄 수 없으니, 3으로 뺄 수 있는지 살펴본다.
뺄 수 있다. 해당 값이 0이면 위로 타고타고 올라가서, 얼마나 거쳤는지를 알려주면 된다.

코드로 구현해보자, 필자는 재귀로 구현하였다. 

int mod(int S) {
    if (S < 0) {
        return -1;
    }

    if (S == 0) {
        return 0;
    }

}

먼저 재귀를 빠져나올 수 있도록 처리를 먼저 해주자 인자 값이, 음수면 -1로 리턴 해주고 0과 같다면 0을 리턴해준다.

int mod(int S) {
    if (S < 0) {
        return -1;
    }

    if (S == 0) {
        return 0;
    }
    if (S >= 5) {
        int count_with_5 = mod(S - 5);
        if (count_with_5 != -1) {
            return count_with_5 + 1;
        }
    }
}

이제, S로 먼저 뺄 수 있는지를 확인하고, 뺼 수 있다면 변수 하나에 S-5를 뺀 만큼 재귀를 돌린다.
이후 해당 값이 -1 이 아니라면, +1을 해주고 리턴해준다.

int mod(int S) {
    if (S < 0) {
        return -1;
    }

    if (S == 0) {
        return 0;
    }
    if (S >= 5) {
        int count_with_5 = mod(S - 5);
        if (count_with_5 != -1) {
            return count_with_5 + 1;
        }
    }

    if (S >= 3) {
        int count_with_3 = mod(S - 3);
        if (count_with_3 != -1) {
            return count_with_3 + 1;
        }
    }
    return -1;
}

3도 같다. 5에서 뺄 수 없으니, 즉 return 이 나오지 않으면,  3을 확인해보고 3에서도 -1이 나온다면 최종적으로 return을 -1로 해준다.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>


using namespace std;

int N;
void Intput()
{
	cin >> N;
}

int mod(int S) {
    if (S < 0) {
        return -1;
    }

    if (S == 0) {
        return 0;
    }
    if (S >= 5) {
        int count_with_5 = mod(S - 5);
        if (count_with_5 != -1) {
            return count_with_5 + 1;
        }
    }

    if (S >= 3) {
        int count_with_3 = mod(S - 3);
        if (count_with_3 != -1) {
            return count_with_3 + 1;
        }
    }
    return -1;
}

void Solution()
{
	cout << mod(N);
}

void Solved() {
	Intput();
	Solution();
}

int main() {
	Solved();
}