[그리디] 백준 4796 캠핑 C++

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

4796번: 캠핑

---

---

풀이 : 

기본적인 그리디 문제라서 푸는데 그리 오래 걸리지 않았다 문제 읽고 이해하고 푸는데까지 10분?20분? 정도 걸린거같은데 계속 틀렸습니다 떠서 아무리 오류를 찾아도 찾지 못해서 코드를 첨부터 다른방법으로 다시 짰다.. 근데 또 틀렸습니다. 나옴.. 알고보니 출력할때 case 를 Case라고 대문자를 C를 써야하는데 소문자 c를 써서 틀린거였음.. 덕분에 풀이는 두가지 !! 오히려 좋다

 

첫번째는 단순히 조건문을 써서 전체 휴가 날에서 P를 빼주는 것! 연속한 P날 짜마다 L일동안 쓰는 거니까 L일 1이라고 치면 8일에 한번 캠핑할 수 있어요~ 이런 식이니까 직관적이다 즉,  전체 휴가 V에서 P를 빼주다가(빼주는 동안 캠핑 이용 횟수 L을 계속 더해준다.) 남은 휴가가 P일보다 작은 경우 고려해줘야 L과 남은V를 비교해서 최솟값을 더해 주면 된다. 직관적으로 생각하면 남은 휴가가 6일인데(V) 이용 가능한 횟수(L)이 7일 이라면 남은 휴가를 모두 더해주고 (ans += V) L이 5일 이라면 이용가능한 날을 모두 더해주면된다 (ans += L)

 

두번째 방법이 조금 더 그리디스러운? 방법인데 앞서 조건문 사용한 방법과 논리는 같으나 더 간결하다 전체 휴가에서 P를 나누고 몫 만큼 L을 더해준다 그리고 위에서 남은 V를 더해줄 것이냐 L을 더해줄 것이냐 조건문으로 판단했는데 남은 V는 V%P로 구하고 L과 비교해서 최소값을 ans에 같이 더해주면 된다

 

코드 1:

#include <iostream>

using namespace std;

int L, V, P;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int ans = 0;
	int cnt = 1;
	// 연속하는 8일V 중 5일L만 사용가능 휴가 20일V
	while (true) {
		cin >> L >> P >> V;
		if (L == 0 && V == 0 && P == 0) break;
		while (true) {
			if (V - P > 0) {
				V -= P;
				ans += L;
			}
			else {
				if (V <= L) {
					ans += V;
					break;
				}
				else {
					ans += L;
					break;
				}
			}
		}
		cout << "Case " << cnt << ": " << ans << endl;
		ans = 0;
		cnt++;
	}

}

 

코드 2:

#include <iostream>
#include <algorithm>

using namespace std;

int L, V, P;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int ans = 0;
	int cnt = 1;
	// 연속하는 8일V 중 5일L만 사용가능 휴가 20일V
	while (true) {
		cin >> L >> P >> V;
		if (L == 0 && V == 0 && P == 0) break;
		ans = (V / P) * L + min(V % P, L);
		cout << "Case " << cnt << ": " << ans << endl;
		ans = 0;
		cnt++;
	}

}