Greedy

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/13448 🧐 관찰 및 접근 # 얻는 점수가 $M_i - t * p_i$가 아닌 $M_i$라면, 단순한 배낭문제일텐데.. 이걸 위해서 $N$에 대한 비트마스킹을 추가하는건 미친짓이다 그런데, 어떤 문제들을 풀기로 결정했다면, 그 문제들에 대해 순서를 정하는건 그리디하게 되지 않나? 문제 $i, j$가 있다고 하자. $i \rightarrow j$로 풀면 $(M_i - t * P_i) + (M_j - (t + R_i)*P_j)$ 점을 얻게 되고 $j -> i$로 풀면 $(M_j - t*P_j) + (M_i - (t + R_j) * P_i)$ 점을 얻게 된다. 위에서 아래 식을 빼면 $P_i * R_j - P_j * R_i$ 이고, $i \rightarrow j$가 이득이기 위해선 이게 양수여야하므로 $\frac{P_i}{R_i} \geq \frac{P_j}{R_j}$로 정렬하는 그리디 전략이 유효하다. 그렇다면 이 순서로 냅색 DP를 수행하자. 💻 풀이 # 코드 (C++): void solve(){ int N, T; cin >> N >> T; vector<Problem> Prob(N); rep(i, 0, N) cin >> Prob[i].M; rep(i, 0, N) cin >> Prob[i].P; rep(i, 0, N) cin >> Prob[i].R; sort(all(Prob), [](Problem &A, Problem &B){ return A.P * B.R > B.P * A.R; }); vector<ll> DP(T+1); for(auto [M, P, R]: Prob) rrep(t, 0, T+1){ if(t - R < 0) break; DP[t] = max(DP[t], DP[t - R] + (M - P*t)); } ll ans = 0; rep(i, 0, T+1) ans = max(ans, DP[i]); cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16225 🧐 관찰 및 접근 # 약간 게임이론적이네. $(A_i, B_i), (A_j, B_j)$ 두가지를 고른다. 이때, $B_i > B_j$라면 $A_j$, $B_i < B_j$라면 $A_i$를 얻게된다. 직관적인것들을 생각해보자. $A_i$가 크고, $B_i$가 작은것들이 있으면 좋겠다. 위 친구들을 $A_i$가 작거, $B_i$가 큰 친구들이랑 매칭시켜서 없애버리면 좋다. $B$가 가장 작은 문제는 언제나 내가 풀게 된다. $B$가 가장 큰 문제는 언제나 상대가 풀게 된다. 이쪽에서 출발해볼까? $B$에 대한 오름차순으로 정렬해보자. 그러면 버릴 문제를 하나 고를 수 있다. 일단 예제를 $B$에 대한 오름차순으로 정렬한 후, $A$만 남기면 $(2, 4, 8, 6)$ 이 된다. 이때 2를 택하고 4를 버려고, 8을 택하고 6을 버리면 10이 된다. 여러개로 생각해보니, 약간 올바른 괄호 문자열 맛으로 되는데… 20만 $O(N^3)$ DP는 안된다이 $\text{DP}[i][j]$: $i$번째까지 봤을때, 여는괄호가 $j$개일때 최댓값 이라고 하면 $O(N^2)$도 된다만… 근데 열리는 괄호는, 생각보다 빠르게 열어줘야한다. 1번을 먹었으니, $(2, 3)$중에 하나는 무조건 열어야 한다. $2$를 먹었다면, $3, 4, 5$중 하나는 무조건 열어야 한다. $3$을 먹었다면, $2, 4, 5$중 하나는 무조건 먹어야 한다. $k$개 먹었다면, $2 \leq i \leq 2*k + 1$ 범위 내에서 한개를 더 먹어줘야한다. 이때 최댓값을 먹어줘야하고, 점 업데이트가 있으니 세그먼트 트리로 되겠다. 세그워킹 ㄱ.ㄱ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> A(N); rep(i, 0, N) cin >> A[i].first; rep(i, 0, N) cin >> A[i].second; sort(all(A), [](pii a, pii b){ return a.second < b.second; }); vector<ll> v; rep(i, 0, N) v.push_back(A[i].first); ST.init(N); rep(i, 0, N) ST.set(i, v[i]); ST.build(); ll ans = v[0]; rep(i, 1, N/2){ auto [val, idx] = ST.seg_walk(1, i*2); ans += val; ST.update(idx, 0); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28433 🧐 관찰 및 접근 # 수열을 원하는 개수의 연속된 구간으로 나누어서 구간의 합이 양수인 개수 - 구간의 합이 음수인 개수를 양수로 만들자. 직관적으로 생각해보자. 지금까지의 합이 양수면 -> 걍 잘라버리는게 이득이다. 지금까지의 합이 음수면 -> 이게 좀 고민이네 다음 놈이 음수면 -> 계속 먹으면 되는데, -100 -100 -100 1 -100 같은 경우에는 한번에 큰덩이로 먹는게 이득일수도 있지 않나? 일단 양수/음수는 묶어서 생각할 수 있을거같고, 음수 친구를 왼쪽/오른쪽으로 보내서 양수 덩어리에 합류시킬지 말지만 고민하면 되는것같다. 그렇다면 양수 / 양수 / 음수 / 양수 / 음수 / 양수 이렇게 생겼을텐데, 이제는 음수인 것이 두개 이상 붙어서 등장하지 않는다. 양수 개수 > 음수 개수라면 1을 출력하면 된다! 양수 개수 = 음수 개수라면 한 칸이 결합 가능한지 생각하면 된다! 양수 개수 < 음수 개수라면 두 칸이 결합 가능한지 생각하면 된다! 이게 두번 확인해야해서 문제지만, 결합 가능하면 무조건 결합한다는 방식이 그리디하게 가능하다. 직관적이긴 하네 라고!!!!!!!! 생각했지만!!!!!!!!! 틀렸다. $[2, -1, -1, 2, -1, -1]$ 의 경우.. $(2, -1), (-1, 2), (-1, -1)$로 묶으면 된다. 그러니까 맘대로 묶으면 안된다는건데…. 그리디 문제 추천받아서 풀던거라 여기서 DP로 틀진 않았고, 솔직히 평소같았으면 세그DP로 튀었을듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> v; ll sum = 0; rep(i, 0, N){ ll x; cin >> x; if(x != 0) v.push_back(x); sum += x; } if(v.size() == 0){ cout << "NO\n"; return; } ll cur = 0; int pcnt = 0, ncnt = 0; for(auto x: v){ if(x > 0){ if(cur <= 0 && cur +x > 0) cur += x; else{ if(cur > 0) pcnt++; if(cur < 0) ncnt++; cur = x; } } else{ if(cur > 0 && cur + x <= 0){ if(cur > 0) pcnt++; if(cur < 0) ncnt++; cur = x; } else{ cur += x; } } // cout << "cur: " << cur << " pcnt: " << pcnt << " ncnt: " << ncnt << "\n"; } if(cur > 0) pcnt++; if(cur < 0) ncnt++; cout << (pcnt > ncnt ? "YES" : "NO") << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11920 🧐 관찰 및 접근 # 배열 $[3, 4, 1, 2, 7, 6]$이 있다고 하자. 처음 한바퀴를 돌면 어떻게 되지? $[3, 1, 2, 4, 6, 7]$이 된다. 이걸 어떻게 해석할 수 있을까? 가장 큰 수는 맨 오른쪽에 고정된다. 다른 수들은, 오른쪽에 붙어있수가 자기보다 작은것들을 왼쪽으로 다 밀고, 오른쪽으로 간다. 오큰수? 스택? 그런맛인데 이거 두번하면 어떻게? $[1, 2, 3, 4, 6, 7]$이 된다. 나 5 안썼었구나 ㅋㅋ 이런 값을 두개정도 들고있다가..? 뭔가 그런느낌…? $K$번 진행한다고 하면, 값을 $K$개정도 들고있다가, 들고있는 값중 젤 작은거보다 작으면 그대로 통과시키고, 그것보다 크다면? 어떻게 되는거지? $[5, 7, 4, 3, 6, 8, 1, 2]$를 해보자. $[5, 4, 3, 6, 7, 1, 2, 8]$ $[4, 3, 5, 6, 1, 2, 7, 8]$ 두개 들고있다가 큰거 만나면 작은값 빼버려서 튀면 되는듯?? 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<int> ans; priority_queue<int, vector<int>, greater<int>> PQ; rep(i, 0, N){ PQ.push(A[i]); if(PQ.size() > K){ ans.push_back(PQ.top()); PQ.pop(); } } while(!PQ.empty()){ ans.push_back(PQ.top()); PQ.pop(); } for(auto x: ans) cout << x << " "; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28068 🧐 관찰 및 접근 # 지금 어떤 책을 읽을 수 있고, $a_k <= b_k$라면, 읽지 않을 이유가 없다. 나머지 $a_k > b_k$들인 책들은 어차피 읽을수록 즐거움이 감소만 하므로, $a_k$가 큰거부터 차례대로 읽으면 되지 않을까? 어떻게 그리디하게 가야하지? 두 책 $i, j$가 있다고 해보자. 이때, 두 책을 $i \rightarrow j$로 읽기 위해선 $F \geq a_i$ $F - a_i + b_i \geq a_j \rightarrow F \geq a_i + a_j - b_i$ 따라서 $F \geq \max(a_i, a_i + a_j - b_i) = \text{Cost}_{i \rightarrow j}$ 같은 방식으로, $j \rightarrow i$로 읽기 위해선 $F \geq \max(a_j, a_i + a_j - b_j) = \text{Cost}_{j \rightarrow i}$ 이 때, $b_i \geq b_j$라고 가정하자. $a_i < a_i + (a_j - b_j)$ $a_i + a_j - b_i \leq a_i + a_j - b_j$ 이 두 식이 성립하므로, 언제나 $\text{Cost}_{i \rightarrow j} \leq \text{Cost}_{j \rightarrow i}$ 따라서 $b$의 내림차순으로 정렬 후 그리디가 성립한다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> v1, v2; rep(i, 0, N){ int a, b; cin >> a >> b; if(a <= b) v1.push_back({a, b}); else v2.push_back({a, b}); } sort(all(v1)); sort(all(v2), [](pii &p1, pii &p2){ return p1.second > p2.second; }); ll cur = 0; for(auto &p: v1){ if(cur < p.first){ cout << 0; return; } cur -= p.first; cur += p.second; } for(auto &p: v2){ if(cur < p.first){ cout << 0; return; } cur -= p.first; cur += p.second; } cout << 1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28448 🧐 관찰 및 접근 # 한 문제당 광기는 $KT$만큼 쌓이고, 해결했을때 $\text{min}(KT, 5K)$만큼 빠지므로 $T \leq 5$라면 문제를 푸는데 광기가 안쌓인다. 어라? 아니네. $KT \leq L$ 조건도 필요하다. 아 이건 문제조건에 있네. 암튼 이 친구들은 어차피 T시간 걸려서 풀기만 하면 상관이 없다. 나머지 문제들에 대해, 어차피 문제를 풀어서 쌓이는 광기의 합은 일정하다. 그러니까, 문제를 해결해서 광기를 줄이는걸 힘내야하지 않을까? 그러면 광기를 많이 해소할 수 있는 문제를 먼저 풀어야하는 거 같은데… 💻 풀이 # 코드 (C++): void solve(){ ll N, L; cin >> N >> L; vector<pll> v; ll ans = 0; rep(i, 0, N){ ll K, T; cin >> K >> T; ans += T; if(T <= 5) continue; v.push_back({K, T}); } sort(all(v), [](pll a, pll b){ return min(a.first * a.second, 5 * a.first) > min(b.first * b.second, 5 * b.first); }); ll cur = 0; for(auto [K, T]: v){ if(cur + K*T > L){ ll rest = cur + K*T - L; ans += rest; cur -= rest; } cur += K*T; cur -= min(K*T, 5*K); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20136 🧐 관찰 및 접근 # 그리디하게, 뽑아야할때 곧 쓸만한걸 남기고, 나중에 쓸만한걸 뽑으면 되지 않을까? 증명해보자. 현재 $N$개의 구멍이 꽉차있고, $A$를 새로 꽂아야한다고 가정하자. 가장 나중에 쓰는걸 뽑는 전략 $G$가 있고, 어떤 최적의 전략 $Opt$가 있다고 가정하자. 이제 $G$가 $Opt$보다 나쁘지 않음을 보이면 된다. 어느 순간, $A$를 꽂기 위해 $G$는 $X$를, $Opt$는 $Y$를 뽑았다. 이때, 이후에 $X$가 먼저 등장한다면, $G$는 한번 더 뽑/꼽을 수행해야하고, $Opt$는 아니다. $Y$가 먼저 등장했다면, $Opt$는 뽑/꼽을 수행해야 하고, $G$는 아니다. 그런데, $G$의 전략 특성상 $Y$보다 $X$가 늦게 등장해야하므로, 언제나 $Opt$보다 $G$가 나쁘지 않다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<queue<int>> nxt(K+1); vector<int> A(K); rep(i, 0, K) cin >> A[i]; rep(i, 0, K) nxt[A[i]].push(i); rep(i, 1, K+1) nxt[i].push(1e9); set<pii> st; // (nxt use, val) vector<bool> inuse(K+1, false); int ans = 0; rep(i, 0, K){ int val = A[i]; if(inuse[val]){ // 이미 꽂혀있다면 st.erase({i, val}); } // 꽂혀있지 않다면 else if((int)st.size() < N){ // 남은 자리가 있으면 inuse[val] = true; } else{ // 남은 자리가 없으면 ans++; pii old = *st.rbegin(); st.erase(old); inuse[old.second] = false; inuse[val] = true; } nxt[val].pop(); if(!nxt[val].empty()) st.insert({nxt[val].front(), val}); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10775 🧐 관찰 및 접근 # 1번 게이트가 제일 쓰기 좋아보인다. 그러므로 1번 게이트를 아낀다고 생각하면, 모든 비행기를 도킹시킬때 갈 수 있는 최댓값으로 도킹시키면 되는 것 같다. 이를 나이브하게 구현하면 한번당 $O(G)$가 걸릴 것이다. 100000 100000 100000 100000 100000 ... 과 같은 테스트케이스를 생각해보면 된다. 따라서 $\text{calc}(g_i) = g_i$ 보다 작거나 같은 살아있는 게이트의 최댓값을 빠르게 찾으면 된다. 이는 유니온파인드로 빠르게 수행 가능하다! merge할때 자신보다 작은 값을 가리키게 하자. 💻 풀이 # 코드 (C++): void solve(){ int G, P; cin >> G >> P; UF.init(G+1); int ans = 0; while(P--){ int g; cin >> g; int rt = UF.find(g); if(rt == 0) break; UF.merge(rt, rt-1); ans++; } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14908 🧐 관찰 및 접근 # 직관적으로 생각해보자 어떤 작업의 보상금 $S_i$가 크다면, 빠르게 작업을 수행하는게 좋다. 어떤 작업을 완료하는데 걸리는 시간 $T_i$가 작다면, 빠르게 작업을 수행하는게 좋다. 이 두가지를 어떻게 동시에 활용할 수 있을까? 어떤 정답 $Opt$가 존재한다고 가정해보자. 이때, $Opt$의 순서중 가운데 두 작업 $W_i, W_{i+1}$을 바꾼다고 해보자. 이 때, 바뀐 순서 $Opt'$가 $Opt$보다 나을 수 있을까? 두 작업을 바꾸면, $Opt' = Opt + S_i * T_{i+1} - S_{i+1} * T_i$가 된다. 다시말해, $S_i * T_{i+1} - S_{i+1} * T_i$ 이 음수라면 더 나은 해법을 찾을 수 있다. 따라서 $S_i * T_{i+1} - S_{i+1} * T_i > 0$인 방향, 즉 $\frac{S_i}{T_i} \geq \frac{S_{i+1}}{T_{i+1}}$ 의 순서로 정렬하면 최적해가 된다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<array<int, 3>> ans; // S, T, idx; rep(i, 0, N){ int S, T; cin >> S >> T; ans.push_back({T, S, i+1}); } sort(all(ans), [](const array<int, 3> &a, const array<int, 3> &b){ if(a[0]*b[1] == a[1]*b[0]) return a[2] < b[2]; return a[0]*b[1] > a[1]*b[0]; }); for(auto &p: ans) cout << p[2] << ' '; } 🔒 구현 코드 잠금