그렇다고 한다! 그리디는 대충 경험만 해보고 넘겨야지
11047
#include <bits/stdc++.h>
using namespace std;
int coin[11];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, index = -1;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> coin[i];
if (coin[i] <= k) index = i;
}
int ans = 0;
for (int i = index; i >= 0; --i) {
if (k < coin[i]) continue;
ans += k / coin[i];
k = k % coin[i];
}
cout << ans;
}11931
#include <bits/stdc++.h>
using namespace std;
pair<int, int> meet[100001];
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> meet[i].second >> meet[i].first;
}
sort(meet, meet + n);
int ans = 0;
int t = 0;
for (int i = 0; i < n; ++i) {
if (meet[i].second < t) continue;
ans += 1;
t = meet[i].first;
}
cout << ans;
}모르겠어서 풀이 보고 풀었다. 끝나는 시간이 빠른 것부터 선택해나가야 함!
2217
#include <bits/stdc++.h>
using namespace std;
int r[100001];
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> r[i];
sort(r, r + n);
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, r[i] * (n - i));
}
cout << ans;
}max 사용 익숙해지기
1026
#include <bits/stdc++.h>
using namespace std;
int a[51], b[51];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
sort(a, a + n);
sort(b, b + n);
int ans = 0;
for (int i = 0; i < n; ++i) ans += a[n - 1 - i] * b[i];
cout << ans;
}흠 같은 실버 문제들인데 dp 문제들보다 체감 난이도가 훨씬 쉽다.
dp 문제를 더 열심히 풀어야 할 듯
11399
ver 1
#include <bits/stdc++.h>
using namespace std;
int person[1001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> person[i];
}
sort(person, person + n);
int ans = person[0];
for (int i = 1; i < n; ++i) {
person[i] += person[i - 1];
ans += person[i];
}
cout << ans;
}ver 2
#include <bits/stdc++.h>
using namespace std;
int person[1001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> person[i];
}
sort(person, person + n);
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += person[i] * (n - i);
}
cout << ans;
}내 뒤에 있는 사람은 모두 내 시간만큼 기다리게 된다. 사람마다 내 시간만큼 +가 되는 것이기 때문에 (내 시간) x (내 뒤의 사람 수) 를 해서 더하면 된다.
2457
ver 1
#include <bits/stdc++.h>
using namespace std;
pair<int, int> date[100001];
int n;
int t = 3001;
int find_next_index(int index) {
for (int i = index; i < n; ++i) {
if (date[i].second <= t) index = i;
}
return index;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
// sort를 위해 end부터 저장
date[i].second = a * 1000 + b;
date[i].first = c * 1000 + d;
}
sort(date, date + n);
int ans = 0, i = 0, next_i;
while (i < n) {
if (date[i].first > 11030) break;
next_i = find_next_index(i);
if (next_i == i) break;
t = date[next_i].first;
i = next_i;
ans += 1;
}
if (date[i].first < 11030) ans = 0;
cout << ans;
}
ver 2
#include <bits/stdc++.h>
using namespace std;
pair<int, int> date[100001];
int n;
int t = 3001;
int find_next_index(int index) {
for (int i = index; i < n; ++i) {
if (date[i].second <= t) index = i;
}
return index;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
// sort를 위해 end부터 저장
date[i].second = a * 1000 + b;
date[i].first = c * 1000 + d;
}
sort(date, date + n);
int ans = 0, i = 0, next_i;
while (date[i].first <= 11030) {
next_i = find_next_index(i);
if (next_i == i) {
cout << 0;
return 0;
}
t = date[next_i].first;
i = next_i;
ans += 1;
}
cout << ans;
}
대박... 직접 풀었다. 대신 너무 오래 걸렸지만..
이전에 푼 문제 덕분에 대충 어떤 식으로 풀어야 할지 감이 잡혔다.
끝나는 시간을 기준으로 sort를 해서 풀면 된다.
10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1
2015 3023
2028 4025
5002 5031
4012 6005
6003 6015
7014 9001
6015 9003
6015 9027
9014 12024
10005 12031예제를 가지고 정렬이 된 모습을 살펴본다.
현재 시간 t보다 시작 시간이 앞서 있는 원소들 중 가장 끝에 있는 원소가 다음 타겟이다.
while문을 돌면서 next_i가 선택 됐을 때, 즉 다음으로 진행이 가능할 때 ans += 1을 해준다.
while문은 시작 날짜가 11월 30일 이전인 경우 계속 돌면 된다. 만약 시작 날짜가 11월 30일 후가 아닌데 더 이상 다음으로 진행이 불가능 해서 멈췄다면 그건 11월 30일까지 꽃을 채우지 못 한다는 뜻이다. 그래서 0을 출력 후 종료해주면 된다.
1541
#include <bits/stdc++.h>
using namespace std;
string str;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> str;
int tmp = 0, multi = 1, ans = 0;
for (char c : str) {
if (c >= '0' && c <= '9')
tmp = tmp * 10 + c - '0';
else {
ans += tmp * multi;
tmp = 0;
if (multi == 1 && c == '-') multi = -1;
}
}
ans += tmp * multi;
cout << ans;
}알아두기
for (char c : str)
for-each문 사용하기
11501
#include <bits/stdc++.h>
using namespace std;
int stock[1000001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int n;
cin >> n;
for (int j = 0; j < n; ++j) {
cin >> stock[j];
}
long ans = 0, maxx = stock[n - 1];
for (int j = n - 2; j >= 0; --j) {
if (stock[j] > maxx) maxx = stock[j];
ans += maxx - stock[j];
}
cout << ans << '\n';
}
}long 사용 주의
1744
ver1
#include <bits/stdc++.h>
using namespace std;
int num[51];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int zero = 0, one = 0, ans = 0;
for (int i = 0; i < n; ++i) {
cin >> num[i];
if (num[i] == 0) {
zero = 1;
i -= 1;
n -= 1;
} else if (num[i] == 1) {
ans += 1;
i -= 1;
n -= 1;
}
}
sort(num, num + n);
int i = n - 1;
while (num[i] >= 0 && num[i - 1] >= 0 && i >= 1) {
ans += num[i] * num[i - 1];
i -= 2;
}
if (num[i] >= 0) ans += num[i--];
// 음수가 홀수 개면
if (i % 2 == 0) {
if (!zero) ans += num[i];
i -= 1;
}
while (i >= 0) {
ans += num[i] * num[i - 1];
i -= 2;
}
cout << ans;
}ver2
#include <bits/stdc++.h>
using namespace std;
long long ans;
void get_sum(vector<int> v) {
while (v.size() > 1) {
ans += v[v.size() - 1] * v[v.size() - 2];
v.pop_back();
v.pop_back();
}
if (v.size()) ans += v[0];
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> vP, vN;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
if (k == 1)
++ans;
else if (k > 0)
vP.push_back(k);
else
vN.push_back(k);
}
sort(vP.begin(), vP.end());
sort(vN.begin(), vN.end(), greater<int>());
get_sum(vP);
get_sum(vN);
cout << ans;
}어찌저찌 맞췄는데 바킹독님 풀이 보니까 벡터를 두 개 쓰면 간단하게 해결되는 거였다...
그리고 sort(, greater<>()) 사용법 익히기. 내림차순 정렬할 때 쓰면 된다.
2170
아 대체 문제가 뭔 말인가 했더니 저기서 x,y는 흔히 생각하는 2차원 좌표의 x,y가 아니었다. 그냥 시작점 x, 끝점 y를 말하는 거였음. 둘 다 x좌표라고 보면 된다.
시간 초과
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
pair<int, int> num[1000001];
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> num[i].X >> num[i].Y;
}
sort(num, num + n);
int preX = num[0].X, preY = num[0].Y;
long long ans = 0;
for (int i = 1; i < n; ++i) {
if (num[i].X > preY) {
ans += preY - preX;
preX = num[i].X;
preY = num[i].Y;
} else if (num[i].Y > preY)
preY = num[i].Y;
}
ans += preY - preX;
cout << ans;
}헐 ios::sync_with_stdio(0);, cin.tie(0); 가 빛을 발했다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
pair<int, int> num[1000001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> num[i].X >> num[i].Y;
}
sort(num, num + n);
int preX = num[0].X, preY = num[0].Y;
long long ans = 0;
for (int i = 1; i < n; ++i) {
if (num[i].X > preY) {
ans += preY - preX;
preX = num[i].X;
preY = num[i].Y;
} else if (num[i].Y > preY)
preY = num[i].Y;
}
ans += preY - preX;
cout << ans;
}입출력 동기화 끊으니까 시간초과 해결됨. 근데 문제 이해하는 데 15분을 썼다.
현재 시작점이 이전 끝점 보다 뒤인 경우 (선분이 이어지거나 겹치지 않고 끊긴다.)
ans에 preX - preY를 더한다. (끊기기 전 선분 길이를 더한다.)
그리고 preX, preY를 업데이트 해준다. (이제 새로운 선분이 기준이 된다.)
그렇지 않았는데 현재 끝점이 이전 끝점보다 뒤인 경우 (선분이 겹치는 상태이다.)
preY를 현재 끝점으로 업데이트 해준다.
ans를 업데이트 하진 않는다. 왜냐하면 아직 선분이 더 이어질 수 있는 상태니까.
for문 탈출 후 마지막에 preY - preX를 더한다.
바킹독님 풀이
// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/c5472861d2ee4a1e8f8c3c60f477f0bc
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
vector<pair<int,int>> events;
int n;
cin >> n;
while(n--){
int l, r;
cin >> l >> r;
events.push_back({l, 1});
events.push_back({r, -1});
}
sort(events.begin(), events.end());
int cnt = 0; // 현재 선의 개수
int tot = 0; // 전체 길이(= 답)
int loc = -1e9; // 현재 위치
for(auto event : events){
if(cnt > 0) tot += (event.X - loc);
loc = event.X;
cnt += event.Y;
}
cout << tot;
}
/*
선의 시작과 끝을 이벤트로 관리해 선이 1개 이상 있는 구간을 계속 더해준다.
*/https://blogshine.tistory.com/120
바킹독님 풀이 보니까 생각지도 못한 방법이었다. 라인 스위핑 알고리즘으로 푸는 문제였나보다🤔
시작점은 저장할 때 {l, +1}로 저장하고 끝점은 저장할 때 {r, -1}로 저장한다. 각각 이벤트를 구분해서 저장해준 거다.
그래서 sort를 하게 되면 같은 좌표일 때 시작점이 끝점 보다 먼저 처리되게 된다.
여기서 cnt는 현재 위치가 시작점인 경우 계속 증가해나간다. 그래서 이전 위치에서 현재 위치까지 선분이 하나라도 있는 경우 cnt가 0보다 커지게 된다. 여러번 그은 곳은 한 번 그은 곳과 똑같다고 했으니 그냥 cnt > 0인 경우면 현재 위치에서 이전 위치를 뺀 결과를 total에 저장하면 된다.
cnt == 0이면 현재 위치까지 그어진 선분이 아예 없는 거다.
대략적으로 이해는 되는데... 직관적으로 이해가 안 된다.
이 문제는 어쩔 수 없이 내 풀이 대로 이해하고 넘어가야겠다.
1700
시간 안에 못 풀었다.. 이제 40분 안에 못 풀면 넘어가기로 했다
https://magentino.tistory.com/88 👍👍
나도 처음엔 저 분처럼 가장 빈도가 낮은 것을 뽑는 전략으로 하다가 꼬였는데
가장 시기가 늦는 걸 뽑는 전략으로 했어야 했다.
맞다 최종적으로 여러 번 쓰이진 않지만 당장 다음에 쓰여야 한다면 안 뽑히고 남아 있는 것이 최적이다.
솔직히 이런 문제는 감으로 최적해가 되는 경우를 세우고 때려맞혀야 하지 않나 싶다;; 그래서 바킹독님이 아닌 것 같으면 그냥 넘어가라고 하신 것 같다.
ver 1
#include <bits/stdc++.h>
using namespace std;
int n, k;
int items[101], multitab[101];
bool is_there[101];
int find_farthest(int cur) {
int idx = 0;
for (int i = 0; i < n; ++i) {
// 멀티탭에 꽂힌 것 중 가장 나중에 나오는 것을 선택
int jdx = -1;
for (int j = cur + 1; j <= k; ++j) {
if (multitab[i] == items[j]) {
if (j > jdx) {
jdx = j;
idx = i;
}
break;
}
}
// 만약 jdx가 업데이트 되지 않았다면 후에 쓰이지도 않는 아이템이라는
// 것임.
if (jdx == -1) idx = i;
}
return idx;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; ++i) {
cin >> items[i];
}
int ans = 0, cnt = 0;
for (int i = 1; i <= k; ++i) {
if (is_there[items[i]]) continue; // 이미 꽂혀 있으면 그냥 지나가기
if (cnt < n) { // 멀티탭에 자리가 있으면 꽂기
multitab[cnt] = items[i];
is_there[items[i]] = 1;
++cnt;
continue;
}
// 없으면 제일 나중에 나오는 것을 뽑음
int idx = find_farthest(i);
is_there[multitab[idx]] = 0;
multitab[idx] = items[i];
is_there[items[i]] = 1;
++ans;
}
cout << ans;
}틀림..
아 바보 다시 보니까 멀티탭 하나 하나마다 jdx가 초기화 돼버린다.
변수 세 개가 필요했다.
ver 2
#include <bits/stdc++.h>
using namespace std;
int n, k;
int items[101], multitab[101];
bool is_there[101];
int find_farthest(int cur) {
int max_future = -1; // 가장 나중에 나오는 시점
int max_idx = 0; // 그 아이템의 멀티탭 인덱스
for (int i = 0; i < n; ++i) {
// 멀티탭에 꽂힌 것 중 가장 나중에 나오는 것을 선택
int next_occur = k + 1; // 초기값은 아예 안 나오는 경우. 그래서 K + 1.
for (int j = cur + 1; j <= k; ++j) {
if (multitab[i] == items[j]) {
next_occur = j;
break;
}
}
if (next_occur > max_future) {
max_future = next_occur;
max_idx = i;
}
}
return max_idx;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; ++i) {
cin >> items[i];
}
int ans = 0, cnt = 0;
for (int i = 1; i <= k; ++i) {
if (is_there[items[i]]) continue; // 이미 꽂혀 있으면 그냥 지나가기
if (cnt < n) { // 멀티탭에 자리가 있으면 꽂기
multitab[cnt] = items[i];
is_there[items[i]] = 1;
++cnt;
continue;
}
// 없으면 제일 나중에 나오는 것을 뽑음
int idx = find_farthest(i);
is_there[multitab[idx]] = 0;
multitab[idx] = items[i];
is_there[items[i]] = 1;
++ans;
}
cout << ans;
}필수 문제 끝!!!
그리디는 빠이... 다른 거 복습부터 해야겠다.
