백준 4796, 1449, 17509 _ 그리디 알고리즘
4796번
https://www.acmicpc.net/problem/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
스티커가 붙어있는지 확인 (+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