백준 4796, 1449, 17509 _ 그리디 알고리즘

4796번

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

4796번: 캠핑

이거 반복

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int L, P, V;

int main()
{
	int cnt = 1;
	while (1)
	{
		cin >> L >> P >> V;	
		if (L == 0 && P ==0 && V == 0)
			break;
		
		int ans = (V / P) * L + min(V % P, L);
		cout << "Case " + to_string(cnt) << ": " << ans << '\n';
		cnt++;
	}

	return 0;
}

---

1449번

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

1449번: 수리공 항승

스티커가 붙어있는지 확인 (+0.5), 만약에 없어서 붙일때는 (-0.5)해서 붙임

입력데이터가 정렬되서 들어오지 않으므로 입력받으면서 동작 수행할 생각하지 말것.ㅎ 내가 그래서 몇번 틀림. 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int N, L;
	int cnt = 0;
	cin >> N >> L;

	double coverable = -1;
	vector<double>leakPoints;
	double leakPoint;
	for (int i = 0; i < N; i++)
	{
		cin >> leakPoint;
		leakPoints.push_back(leakPoint);
	}

	sort(begin(leakPoints), end(leakPoints));
	for (auto& ele : leakPoints)
	{
		if (ele + 0.5 > coverable)
		{
			coverable = ele - 0.5 + (double)L;
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

---

17509

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

17509번: And the Winner Is... Ourselves!

해석을 잘못해서 좀.. 그랬다. v는 단발성인걸 생각하면 걍 time만 오름차순 정렬하여 풀면됨.

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool comp(const pair<int, int>& a, const pair<int, int>& b)
{
	return a.first < b.first;
}

int main()
{
	vector<pair<int, int>>problems;
	int t, v;
	for (int i = 0; i < 11; i++)
	{
		cin >> t >> v;
		problems.push_back({ t, v });
	}
	sort(begin(problems), end(problems), comp);

	int time = 0;
	int V = 0;
	int total = 0;
	for (int i = 0; i < 11; i++)
	{
		time += problems[i].first;
		V = problems[i].second;
		total += (time + V * 20);
	}
	cout << total;
	return 0;
}

---

후기

쉬는시간에 인터넷 서칭하다가 발견한 블로그에서 여러 알고리즘을 잘 설명하여 보다가 추천문제도 있어 풀어보았다. 한동안은 이 블로그에 있는 추천문제들을 풀듯하다.

https://m.blog.naver.com/kks227/220775134486

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)