백준) 4796 캠핑

4796. 캠핑

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 

5 8 20
5 8 17
0 0 0

예제 출력 

Case 1: 14
Case 2: 11

1. 접근

그리디 알고리즘을 적용할 수 있다.

V일을 P일 단위로 나누고, 매 단위마다 어떤 날부터 연속으로 L일 만큼 사용해야 최대한 많이 사용할 수 있는지 묻는 문제다.

2. 풀이

거창하게 그리디로 분석하지 않아도, 직관적으로 생각해보면

V일을 P일 단위로 나누고 남은 짜투리 일은 P일 보다 작을 것이므로, 전부 이용할 수 있다.

또한 P일 단위들은 어떤 날부터 시작하든지 L일만큼 자유롭게 사용할 수 있다.

(0일 부터 L-P일 전까지만 시작하면 최대 L일을 연속으로 쓸 수 있다.)

따라서 (V / P) * L 일 + 짜투리 일 만큼이 정답이 될 것이다.

탐욕적으로 선택해 나가는 방법을 생각해보자면, V일을 처음부터 P일로 연속적으로 나눠가는 것이 당연히 최적해이다.

처음부터 나누지 않으면 당연히 손실이 발생한다. 나머지 짜투리 또한 당연히 첫날부터 최대한 이용(L일 까지)하는 것이 이득이다.

3. 코드

#include <stdio.h>
using namespace std;
 
int l, p, v, i;
 
int main() {
    while (1) {
        scanf("%d %d %d", &l, &p, &v);
        if (!l && !p && !v)
            return 0;
 
        i++;
        int tmp = v % p;
        if (tmp < l)
            printf("Case %d: %d\n", i, v / p * l + tmp);
        else
            printf("Case %d: %d\n", i, v / p * l + l);
    }
}