[Greedy] 백준 4796: 캠핑

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

 

예전에 설탕 문제 풀었던 것을 기억하자.

 

https://gaebaldosamoodosa.tistory.com/79

 

연속된 P일 중 L일만 사용 가능하다는 것을 일종의 큰 상자로 생각하자. 요컨대 박스 무게는 P이고 안에 포장 빼고 실제 내용물이 L 들어 있는 것이다. 그리고 남는 여분은 작은 상자로 포장된다고 생각하자.

 

큰 상자를 고르는 것이 다른 상자의 선택에 영향을 미치지 않고, 매 순간 가능하다면 작은 상자 대신 큰 상자를 선택하는 것이 결국 가장 많은 내용물을 가져가는 결과를 도출할 것이다.

 

다시 말해 한 단계의 선택의 다음 단계의 선택에 영향을 미치지 않고, 매 순간 최적의 해가 문제 전체의 최적의 해가 될 것이기 때문에 Greedy 알고리즘을 사용하는 것이 최적해를 보장한다.

 

즉 강선이가 캠핑 가능한 날을 최대한 연속된 P일로 나누고, 그 값에 *L을 한 후, 나머지는 L보다 크면 L을, L보다 작으면 나머지만큼을 취하는 것이 정답이다.

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int P, L, V;
    int caseNum = 0;
    while(true)
    {
        caseNum++;
        cin>>L>>P>>V;

        if(L==0&&P==0&&V==0) break;

        int quotient;
        int remainder;

        quotient = V/P;
        remainder = V%P;

        int answer = quotient*L;

        if(quotient)
        if(remainder<=L)
        {
            answer+=remainder;
        }
        else{
            answer+=L;
        }

        cout<<"Case "<<caseNum<<": "<<answer<<"\n";
    }
    
}

 

사실 Greedy에 대해 아직 직감이 오지 않고 이 문제도 Greedy 라는 것을 생각했다기보다는 문제집에 태그가 Greedy로 걸려 있어서 내가 끼워맞춘 것에 가깝다. 더 많은 문제풀이 경험을 통해 직관을 길러야겠다..