[C/C++]백준 4796_캠프, 그리디 알고리즘

그리디 알고리즘을 공부하다가 관련 문제를 풀어보기 시작했다

간단하게 그리디 알고리즘이란 지금 순간에서 최적의 답을 선택해서 적합한 결과를 도출해내는 알고리즘이다.

예를 들어 양갈래 길이 여러개 있는 길을 갈때 갈림길에서 그 순간에 제일 적게 걸리는 길을 선택해 가며 가는 방법인데

굉장히 합리적으로 보일 수 있지만 장기적으로는 적합하지 않은 방법일 수 있다. 순간의 최적의 해지만 전체로는 최적의 해가 아닐 가능성이 높기 때문이다.

출처-나무위키 그리디 알고리즘

위와 같이 서울에서 부산을 갈때 잘 동작한다. 그리디 알고리즘은 탐욕 선택 속성과 최적 부분 구조 특성을 가지는 문제들을 해결하는데 강점이 있는데 서울에서 부산을 바로 갈때는 그리디 알고리즘이 부적합하지만 서울에서 대구를 거쳐 부산을 가야하는 특수한 경우에는 최적의 요건을 충족시킨다고 보는 것이다.

 

어쨌든 그리디 알고리즘은 100프로 최적해를 보장해주지 않지만 어느 정도 적합한 수준의 해답을 알려준다.

따라서 정해져있는 코드가 없으며 문제의 맥락을 본 다음 우리가 그리디 알고리즘을 사용할지 말지 판단하게 되는 것이다.

 

• 일반적으로 최대한 적은, 최대한 많은 이라는 특수한 문구가 문제에 들어갈때 사용한다.
• 문제를 읽고 자체적으로 판단해야 하는 경우가 많다.
• 정렬을 한 뒤 사용하는 경우가 많음.

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	
	int count=1;
	while(1){
		int L=0, P=0, V=0;
		cin >> L >> P >> V;
		
		if(L==0)
			break;
			
		cout << "Case " << count++ << ": "  << (V/P)*L + (V%P>L ? L:V%P) << endl;	
	}	
	
	
	return 0;
}

처음에 실패했는데 출력되는 부분에서 조건을 하나 놓쳤다.

예를 들어 20일동안 휴가를 갈때 8일동안 3일 캠핑장을 이용할 수 있다고 할때

16일동안 6일을 이용하고 4일이 남는다. 그런데 캠핑장은 4일동안 3일만 이용할 수 있으니

예외 조건을 잘 따져보고 결과값을 출력해야했다.

이때 (V/P)*L + (V%P>L ? L:V%P) 코드에서 ?를 사용했는데 이는 앞의 조건을 만족하면 A:B 부분에서 A를 만족하지 않는다면 B를 출력하는 연산자다.