[BAEKJOON 4796번] (C++) 캠핑

문제 링크

4796번: 캠핑

• 주어진 P를 기준으로 V에 대하여 최소한의 나머지를 가질 때까지 나눈다.
• 해당 P마다 L일을 사용할 수 있으므로 나눈 몫에 L을 곱하여 사용하는 날로 정한다.
• 나눈 나머지에 대하여 L을 기준으로 비교하여 L보다 작거나 같은 만큼을 사용하는 날로 정한다.
• 사용하는 날을 모두 더하여 최대 며칠동안 사용할 수 있는지 출력한다.

L에 대하여 P를 기준으로 최대한 쉴 수 있는 날짜를 먼저 정한 후 나머지에 대하여 계산하는

그리디 알고리즘을 통하여 해결한 문제였다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

struct inputData {
	int L;
	int P;
	int V;
};

vector<inputData> input;
int l, p, v;
inputData tmpInput;

int Solution(int i)
{	
	int tmp = input[i].V % input[i].P;
	if (tmp > input[i].L)
		return input[i].V / input[i].P * input[i].L + input[i].L;
	else
		return input[i].V / input[i].P * input[i].L + tmp;

}

int main()
{
	do  {		
		cin >> l>> p>> v;
		tmpInput.L = l;
		tmpInput.P = p;
		tmpInput.V = v;
		input.push_back(tmpInput);
	} while (l != 0 && p != 0 && v != 0);

	for (int i = 0; i < input.size() - 1; i++)
	{
		printf("Case %d: %d\n", i + 1, Solution(i));
	}
	return 0;
}

결과