BaekJoon(2839)::설탕 배달

문제

2839번: 설탕 배달

문제파악

: 설탕의 무게가 주어지고 2개의 봉지가 주어지어 더 적은 봉지로 나눌 수 있게한다.

: 즉, 최소 봉지개수를 구해야한다.

 

문제해결

: 최대한 적은 봉지의 개수 > 우선 여러 해결방법중 'greedy algorithm'을 생각할 수 있다.

: 선택은 5kg 그리고 3kg을 선택할 수 있다.

1. 5kg을 선택시 이후 선택에 영향을 주지 않음을 통해 '탐욕스런 선택 조건이 만족 됨을 알수 있다.'
2. 5kg부터 선택해나가다 3kg을 선택하여 전체 봉지의 갯수를 구할 수 있다 : '최적부분 구조조건'

소스코드

#include<iostream>
using namespace std;

int main() {
    int n, result = 0;
    cin >> n;

    while (n > 0) {
        if (n % 5 == 0) {
            n -= 5;
            result++;
        }else if (n % 3 == 0) {
            n -= 3;
            result++;
        }
        else if (n > 5) {
            n -= 5;
            result++;
        }
        else {
            result = -1;
            break;
        }
    }

    cout << result;

    return 0;
}

 

: 우선 최선의 선택이 무엇이 될지가 중요하다. 즉, 우선 선택으로 선택해야하는 조건을 잘 구분해 두어야한다.