[PS][Greedy] Chapter 0
그리디 알고리즘 입니다. 대표적인 유형을 보겠습니다.
브론즈 문제
설탈 배달
5키로짜리를 최대한 가져가고 나머지는 3키로짜리로 남김없이 가져갈 수 있는지 판단합니다. 안된다면 5키로짜리를 하나씩 줄이면서 3키로짜리로 남김없이 가져갈 수 있는지 확인합니다.
#include <iostream>
using namespace std;
int main(void) {
int n = 0;
cin >> n;
int d = n / 5;
int r = 0;
for (int i = d; i >= 0; i--) {
r = n - 5 * i;
if (r % 3 == 0) {
cout << i + r / 3 << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
거스름돈
설탕배달 문제에서 거스름돈의 종류를 늘린 문제입니다. 역시 가장 큰 동전부터 최대한 많이 가져갑니다.
#include <iostream>
using namespace std;
int main(void) {
int n = 0;
cin >> n;
n = 1000 - n;
int arr[6] = { 500,100,50,10,5,1 };
int ans = 0;
int i = 0;
while (n) {
ans += n / arr[i];
n -= (n / arr[i]) * arr[i];
i++;
}
cout << ans << "\n";
return 0;
}
컵홀더
솔도 또는 커플을 A라고 생각하고 컵홀더는 -라고 표기하겠습니다.
- A - A - A -에서 모든 A는 자신의 왼쪽의 -를 사용하면 하나가 남습니다. 이 때 A가 솔로인 경우는 모두 자신이 가진 -와 사라질 수 있어서
- A - A -라고 표시하겠습니다. 이렇게 남은 A는 LL이기 때문에
- LL - LL -이고, 결국 가장 오른쪽에 남은 -는 “커플이 존재할 때 가장 오른쪽에 있는 커플 중 오른쪽에 있는 사람의 컵홀더로 쓰일 수 있다.” 는 의미를 가집니다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
char c;
cin >> N;
fgetc(stdin);
int cnt = 0;
for (int i = 0; i < N; i++) {
cin >> c;
if (c == 'L') {
cnt++;
}
}
if (cnt) {
cout << N - cnt / 2 + 1 << "\n";
}
else {
cout << N << "\n";
}
return 0;
}
UCPC는 무엇의 약자일까?
UCPC 각 문자열이 등장하면 인덱스를 올려서 각 문자가 등장했는지 여부를 판단합니다. cpp에서 line을 입력받을 때는 getline(cin,s)를 사용합니다.
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
getline(cin, s);
char arr[4] = { 'U','C','P','C' };
int j = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == arr[j]) {
j++;
if (j == 4) {
cout << "I love UCPC" << "\n";
return 0;
}
}
}
cout << "I hate UCPC" << "\n";
return 0;
}
실버 문제
동전 0
가장 큰 동전부터 접근합니다.
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k, i;
int arr[10];
cin >> n >> k;
for (i = 0; i < n; i++) {
cin >> arr[i];
}
int ans = 0;
while (k) {
i--;
ans += k / arr[i];
k %= arr[i];
}
cout << ans << "\n";
return 0;
}
잃어버린 괄호
-가 한 번이라도 나오는 순간 그 뒤의 숫자는 모두 뺄 수 있습니다. 0부터 시작하는 경우 scanf(“%d”)로 받으면 됩니다. scanf로 char를 받아서 c != 10는 ascii 개행문자 New Line이 아닌지 확인하는 부분입니다.
#include <cstdio>
#include <string>
using namespace std;
int main(void)
{
int ans = 0;
char c;
int oprd;
bool negative = false;
scanf("%d", &ans);
while (scanf("%c", &c), c != 10) {
scanf("%d", &oprd);
if (c == '-') negative = true;
if (negative) ans -= oprd;
else ans += oprd;
}
printf("%d\n", ans);
return 0;
}
string으로 받으면 substr을 사용해서 풉니다.
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int ans = 0;
int prev = 0;
bool flag = false; //한번이라도 - 가 나오면 그 뒤는 모두 -로 바꿀 수 있다.
for (int i = 0; i <= s.size(); i++) {
if (s[i] == '+' || s[i] == '-' || i == s.size()){
if (prev == 0) {
ans = atoi(s.substr(prev, i - prev).c_str());
}
else {
if (flag) {
ans -= atoi(s.substr(prev, i - prev).c_str());
}
else {
ans += atoi(s.substr(prev, i - prev).c_str());
}
}
if (s[i] == '-') {
flag = true;
}
prev = i + 1;
}
}
cout << ans << "\n";
return 0;
}
나무 자르기
나무가 n개이고 n번 자르기 때문에 그리디 알고리즘이 간단해집니다. 똑같은 나무를 여러 번 자르면 한 번도 안 자른 나무가 생기게 됩니다. 이제 여러 번 잘랐던 나무를 마지막에 한 번만 자르고 나머지 횟수로 안 잘랐던 나무를 자르면 더 긴 길이를 얻을 수 있습니다.
만약 나무가 N개이고 자르는 횟수가 N보다 작다면 더 어려운 문제가 됩니다.
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n = 0;
pair<int,int> arr[100100];
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main(void)
{
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i].first);
}
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i].second);
}
sort(arr, arr+n, compare);
long long ans = 0;
for (int i = 0; i < n; i++) {
printf("%d %d\n", arr[i].first, arr[i].second);
ans += arr[i].first + arr[i].second * i;
}
printf("%lld", ans);
return 0;
}
회의실 배정
문제의 정답은 여기에서 확인할 수 있습니다.
- 가장 먼저 끝나는 회의를 선택해야합니다. 만약 이를 선택하지 않으면 가장 먼저 시작하는 회의가 늦게 끝날 뿐입니다.
- 매 순간 순간 가장 먼저 끝나는 회의를 진행합니다.
평행 우주
#include <iostream>
using namespace std;
int n;
int spd[300000];
int main(void) {
cin >> n;
int i = 0;
for (i = 0; i < n; i++) {
cin >> spd[i];
}
long long ans = 0;
for (i = n - 1; i >= 0; i--) {
if (ans < spd[i]) ans = 1LL * spd[i];
else if (ans == spd[i]) continue;
else {
if (ans % spd[i] == 0) continue;
ans = 1LL * ((ans / spd[i]) + 1) * spd[i];
}
//cout << ans << "\n";
}
cout << ans << "\n";
return 0;
}
- 가장 마지막에 도착해야하는 행성의 속도부터 확인
- 행성을 지날 수 있는 가장 작은 배수를 저장