[백준알고리즘] 4796번: 캠핑 -C++

[백준알고리즘] 4796번: 캠핑 -C++

4796번: 캠핑 (acmicpc.net)

4796번: 캠핑

그리디의 다른 쉬운 문제를 풀었다. 이 문제도 예전에 풀었던 ATM 문제와 같이 SJF 방식으로 풀면 된다.

 

이게 그리디지 ㅋㅋ 하면서 쉬워서 기분 좋았다.

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

어떤 경우에서든 연속된 \(P\) 일 중에 최대 \(L\) 일만 사용할 수 있어야 한다. 즉, \(V+0 \sim V+P+0\) 까지도 \(L\) 일만 사용해야 하고, \(V+1 \sim V+P+1\) 까지도 \(L\) 일만 사용해야 한다.

 

이럴 때 그냥 최대한 빨리 캠핑장을 쓰면 된다. 안된다고 할 때만 안 쓰면 된다. 그럼 언제나 만족하게 된다.

즉, \(V+0 \sim V+L\)까지 무조건 쓰고, \(V+L+1 \sim V+P+0\) 까지는 안 쓰면 된다. 그리고 쿨타임 돌 때마다 쓰면 된다.

 

그래서\(V/P*L\)까지 최대한 쓴다. 그럼 \(P\)로 나눠떨어지지 않은 일수가 있는데 그때도 마찬가지로 최대로 쓸 수 있는 만큼(\(<= L\)) 사용하면 된다.

 

아래의 코드처럼 작성했다. 코드 자체를 줄일 수 있는 부분이야 더 있겠지만, 가독성을 위해 이렇게 하고 마무리했다.

#include <cstdio>

int main(void) {
	for ( int iCase = 1; ; ++iCase ) {
		/* 입력 */
		int L, P, V;
		scanf("%d %d %d", &L, &P, &V);
		if ( 0 == L && 0 == P && 0 == V ) {
			break;
		}

		/* 최대 일 수 */
		int iMax = (V / P) * L + ((V % P) < L ? (V % P) : L);

		/* 출력 */
		printf("Case %d: %d\n", iCase, iMax);
	}

	return 0;
}