03.01. 캠핑[Greedy Algorithm][백준 4796]

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

4796번: 캠핑

 

Algorithm classification : Greedy Algorithm, Math

03.01.1. Problem

Kang-San Kim is with his family. It has a reasonable price. Only available for 10 days out of 20 consecutive days. Kang San has just taken a 28-day vacation. Would you like to go shopping for Kang San during the vacation? I want strong acids to generalize a bit more. Of the P days that the chapter continues, only L days. Kang San enjoyed her vacation to the fullest. Kang San Yi for the shortest period of time? (1 < L < P < V)

 

03.01.2. Input limit

The input consists of several test cases. Each test case consists of a single line and contains L, P, V in that order. All input integers are int range. Three zeros are given in the last line.

 

03.01.3. Output

For each test case, the maximum number of days that Sani Kang can use the campground is printed as an example output.

 

03.01.4. Solution

매우쉬운 문제죠. 월급을 가능한 빨리 받고 싶은 것처럼 사용가능한 날 중 가장 빨리 기간을 잡고 사용하면 됩니다. 그러면 L일 동안 캠핑하고 P-L일 동안 못하고를 반복하게 되죠. 어쨋거나 P일씩 구간을 잡는 것이니 Greedy choice property를 만족합니다. 앞의 P일 동안 선택을 어떻게 하더라도 P일 이후의 선택에 영향을 주지 않기 때문입니다.

	for(i = 1;;i++){
		scanf("%d %d %d", &l, &p, &v);
		if(l * p * v == 0) break;
		printf("Case %d: %d\n", i, v/p*l + (v%p > l ? l : v%p));
	}