백준 2839_설탕 배달.cpp

<소스코드>

#include <iostream>
using namespace std;
int main(){
	int kg;
    int maxcnt = 10000;
    int cnt = 0;
    int answer = -1;
    cin >> kg;
    int tempkg = kg;
    if(kg%5 == 0){
    	
        answer = kg/5;
    }else if(kg%3 == 0){
        while(kg > 3){
            kg -= 5;
            cnt++;
            if(kg%3 == 0){
                if(cnt + kg/3 < maxcnt){
                    maxcnt = cnt + kg/3;
                }
            }
        }
        if(maxcnt != 10000) { answer = maxcnt;}
        else{answer = tempkg/3;}
        
    }else{
        while(kg > 3){
            kg -= 5;
            cnt++;
            if(kg%3 == 0){
                if(cnt + kg/3 < maxcnt){
                    maxcnt = cnt + kg/3;
                }
            }
        }
        if(maxcnt != 10000){ answer = maxcnt;}
    }
    cout << answer << endl;
    return 0;
}

1. 변수
   int kg : 입력받은 kg
   int maxcnt : 가장 적은 가방
   int cnt : 가방 개수
   int answer : 구하고자 하는 값
   int tempkg : 임시 kg수

2. 알고리즘
   1) kg이 5의 배수라면 answer은 나눈 몫을 출력한다.
   2) kg이 3의 배수인 경우

• k>3일때까지 5를 순차적으로 빼주며 가방을 추가해줌
• kg가 3의 배수이면 최소로 만드는 봉지수를 구함
• 그것이 이전에 나온 값보다 작으면 바궈줌
  => 이때 3의 배수에 나머지(1,2)가 마지막에 나오는 경우 => answer = 3의로 나눈 몫
  3) 둘다 아닌 경우(3의 배수, 5의 배수가 아닌 경우)
• 3의 배수일때와 알고리즘은 똑같지만 나머지가 마지막에 나오는 경우에 answer = -1

3. 배운점
   사실 정말 노력해서 푼 문제지만 코드 상에서 배운 이론적 지식은 없다. 그러나 다른 코드를 찾아보면서 느낀것이 있다.

#include <iostream>
using namespace std;
int N;
int main() {
	cin >> N;
	int ans = 0;
	while (N>=0) {
		if (N % 5 == 0) {	//가장 큰 수로 나누는게 가장 작은수랑 섞어서 나누는 것보다 유리
			ans += (N / 5);	//나눈 몫을 더한 것이 정답
			cout << ans << endl;
			return 0;
		}
		N -= 3;	//3kg을 빼고 
		ans++;	//가방 하나 늘어남
	}
	cout << -1 << endl;
}

greedy algorithm : 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법

• 코드를 살펴보면 일단 5로 모두 나눠 담을 수 있는지를 확인하고 그것이 아니라면 3kg를 하나만 뺀다. 이를 반복하다가 만일 설탕이 음수가 되면 -1을 출력한다!
  즉 5kg로 나눌 수 있을때 모두 나눠버리기 때문에 현재 상황에서의 최적의 해만 쫓는 그리디 알고리즘임을 알 수 있다.

4. 아쉬운점&느낀점
   아쉽기보단 알고리즘을 풀면서 정해진 알고리즘? 오늘 나온 greedy라던지 이전에 봤던 재귀라던지 이런 알고리즘을 정확히 몇개 알고있고 문제를 보면서 바로 아 이 알고리즘을 사용해야겠다라는 레벨이 되고 싶다. 이렇게 하려면 내가 자기개발비용을 샀던 책을 읽어야 된다. 조금씩 알고리즘을 익혀야겠다.