[백준 / 4796] 캠핑 - C++

www.acmicpc.net/problem/4796

4796번: 캠핑

문제 : 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다. 

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

 

입력 : 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

 

출력 : 각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력한다.

 

그때그때 할 수 있는 최적의 방법을 수행한다는 그리디 알고리즘을 이해하고 있다면 쉽게 풀이할 수 있는 문제이다.

 

만약 휴가가 30일 주어지고 캠핑장은 10일 중 3일만 사용할 수 있다고 생각하여 보자. 

• 캠핑장은 10일을 주기로 아무때나 3일 사용할 수 있다.
• 따라서 30일을 10일 10일 10일로 나누어 생각해보면 캠핑장은 최대 9일만을 사용할 수 있다는 것을 알 수 있다.

이번에는 만약 휴가가 30일 주어지고 캠핑장은 8일 중 7일만 사용할 수 있다고 생각하여 보자. 

• 캠핑장은 8일을 주기로 아무때나 3일 사용할 수 있다.
• 따라서 30일을 8일 8일 8일로 나누어 생각해보면 캠핑장은 21일만을 사용할 수 있고 6일이 남는다는 것을 알 수 있다.
• 남은 6일 중 캠핑할 수 있는 날짜는 6일 전부이다.
• 따라서 30일 동안 캠핑장을 최대로 사용할 수 있는 기간은 21 + 6  = 27일이다.

위 경우의 수를 모두 생각하여 풀이해보면 (V/Z)*L + min(L, (V%P))라는 식 하나로 해결할 수 있다.

#include <iostream>
using namespace std;

int main(){
    long long x,y,z,c=1;
    while(1){
        scanf("%d %d %d",&x,&y,&z);
        if(x==0){
            break;
        }
        printf("Case %d: %d\n",c,(z/y)*x + min(x, (z%y)));
        c++;
    }
}