[백준OJ] 4796번 캠핑

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

4796번: 캠핑

---

 

-풀이-

문제에 나온 예시를 먼저 보자.

20일동안 연속되는 날중 10일만 사용할 수 있고, 방금 28일 휴가를 떠났을때 최대 사용가능한 날을 구해보자.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40

파란색이 이용가능한 날이고, 빨간색은 이용이 불가능한 날이다. 따라서 최대 18일을 이용할 수 있다는것이다.

 

하나하나 살펴보자.

처음 1일~20일중 강산이는 연속되는날중 10일을 사용할 수 있다. 따라서 1~20중 연속되는 10일을 사용가능하다.

다음 21~40일중 강산이는 연속되는 날 중 10일을 사용 할 수 있다. 하지만 강산이는 28일날까지 휴가이므로, 강산이가 최대로 사용을 하기 위해선, 21~30까지 캠핑장을 사용해야, 21~28일까지 총 8일을 더 이용할 수 있게된다.

따라서 최대 18일동안 이용이 가능하다.

 

8일동안 연속되는 날 중 5일만 사용할 수 있고, 방금 20일의 휴가를 떠났을때의 경우를 구해보자.

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24

위와같이 따져보자.

처음 1~8일중 강산이는 최대 5일을 사용할 수 있다.

9~16중 강산이는 최대 5일을 사용할 수 있다.

17~24중 강산이는 총 5일을 사용할 수 있다. 하지만 강산이는 20일까지 휴가이므로, 17~21동안 사용을 한다고 해야 최대 4일을 사용할 수 있다.

따라서 강산이는 총 14일을 사용할 수 있게된다.

 

규칙이 보이는가?

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 라고할때

V/P 만큼의 묶음은 최대 L일을 모두 사용할 수 있다.

나머지 날짜인 V%P 일동안 최대 사용할 수 있는 날은, V%P가 L일보다 작다면, 남은 날짜인 V%P일이 최대가 되는것이고, V%P가 L일보다 크다면, 최대 L일 사용할 수 있게되는것이다.

 

-시간복잡도-

단순 계산식이므로, 테스트케이스가 T개라고 한다면 O(T)가 된다.

 

-코드-

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int l, p, v;
	int n = 1;
	while (true) {
		cin >> l >> p >> v;
		if (!l && !p && !v) {
			break;
		}

		int result = (v / p)*l;
		v %= p;
		result += (l < v ? l : v);
		cout << "Case " << n << ": " << result << "\n";
		n++;
	}
}