📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28359 🧐 관찰 및 접근 # 일단 모두 $P$에 몰아넣거나, $Q$에 몰아넣거나는 가능하니 일단 기본적으로 모든 원소의 합정도는 여유롭게 가능하다. 그런데, 모든 수가 같다고 생각해보자. 그러면 모든 수는 $P$와 $Q$에 동시에 속하는데… 동시에 속할 수 있는 수를 어떻게 제어할 수 있지? 동시에 속한 수가 서로 다른 여러개의 수일 수는 없다. 어떤 수와 그 개수를 곱한 값이 최대인 수를 골라서, 맨 뒤로 보내자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; map<int, int> mp; int ans = 0; rep(i, 0, N){ int x; cin >> x; mp[x]++; ans += x; } int mxIdx = -1, mxVal = -1; for(auto [k, v]: mp){ if(k*v > mxVal){ mxVal = k*v; mxIdx = k; } } ans += mxVal; vector<int> v1, v2; for(auto [k, v]: mp){ if(k < mxIdx) rep(i, 0, v) v1.push_back(k); else if(k > mxIdx) rep(i, 0, v) v2.push_back(k); } rrep(i, 0, v2.size()) v1.push_back(v2[i]); rep(i, 0, mp[mxIdx]) v1.push_back(mxIdx); cout << ans << '\n'; for(auto x: v1) cout << x << ' '; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16940 🧐 관찰 및 접근 # 풀이1 문제 그대로 큐에 넣으면서 시뮬레이션해볼 수 있겠다. 같은 레벨 안에서 원하는대로 선택할 수 있으니, 다음으로 들려야하는걸 셋으로 잘 관리하면서 해보자. 풀이2 현재 내가 있는 노드, 그리고 다음 노드를 큐에 넣을 수 있는지를 체크하는 노드 두가지로 문제를 시뮬레이션하자. cidx에서 nidx로 갈 수 있으면 nidx++를 하고, 없을때 cidx를 ++하자. nidx가 N에 닿지 못했다면 불가능한 것이다. 이 풀이는 트리가 아닌 그래프에서만 가능하다! 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> links(N+1); rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } vector<int> order(N); bitset<100001> visited; rep(i, 0, N) cin >> order[i]; queue<set<int>> v; v.push({1}); visited[1] = true; int idx = 0; while(idx < N){ set<int> nset; while(!v.empty() && v.front().empty()) v.pop(); if(v.empty()){ cout << 0; return; } if(v.front().count(order[idx]) == 0){ cout << 0; return; } int cur = order[idx]; v.front().erase(cur); for(int nxt: links[cur]){ if(visited[nxt]) continue; visited[nxt] = true; nset.insert(nxt); } v.push(nset); idx++; } cout << 1; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17364 🧐 관찰 및 접근 # 어… 문제가 상당히 곤란해보인다. ㅋㅋㅋㅋ 첫번째 예제부터 친절해서 망정이지, 저런거 없었으면 당연히 1357번 1등한테 먹이고 3 출력했을 것 같다. $K = 1$일때부터 풀어보자. 이때는 자명하게도 회의실 배정 문제와 같다. 끝나는 시간을 기준으로 정렬하고, 그리디하게 가져가자. $K = 2$라면? 형섭이는 1등이 먹고 남은 대회들에 대해서, 결국 위의 그리디한 방법으로 가져갈 것이다. 이 때, 1등이 1, 3, 5, 7번 대회를 가져가서 남은 대회가 $(2, 3), (4, 5), (6, 7)$ 이라면 3개를 먹는 것이고, 1, 4, 7번째 대회를 가져가서 남은 대회가 $(2, 3), (3, 4), (5, 6), (6, 7)$ 이라면 2개밖에 못먹는 것이다. 이걸 DP같은걸로 어떻게 잘 가져가면 좋을것같은데.. 엥? 근데 이거 약간 그리디하게 되지 않을까? 형섭씨도 그리디하게 먹으려고 하니, 형섭씨의 그리디를 의도적으로 방해하자. 제일처음에 시간은 $T = 0$일때, 형섭씨는 첫번째 대회 $(1, 2)$를 출전하려고 한다. 바아로 1등 출동 힝잉잉거리면서 두번째 대회 $(2, 3)$을 출전하려고 한다. 이걸 막을수는 없다. 그런데 이걸 나가고 나면 $(3, 4)$ 까지는 못나가시니 절대 안막아버리기 그다음에 $(4, 5)$ 대회를 나가시려고하면, 이때 첫번째 대회 나가신분은 퇴근 후 집에서 요양중이시다. 바로 저기 보내버리자. 다시 형섭씨는 힝잉잉거리면서.. 어쩌구 우선순위 큐로 관리하면서 그리디하게 진행할 수 있을 것 같다!!!!!!! ㅠ.ㅠ 바로 틀렸다. 이것만으로는 상대방이 너무 많은 대회를 나갈 수 있는 것 처럼 된다. 아하, $(3, 5), (4, 5), (2, 7)$이 있다고 해보자. 단순하게 끝나는 시간만 관리해서는, 5일에 나와서 퇴근 후 저 $(2, 7)$ 대회에 나갈 수 있는것처럼 내가 해버렸다. 이러면 안되지 음.. 어차피 세개 다 무조건 못먹는건 맞는데. 그리디라고 생각하면.. 쓸 수 있는 놈중 가장 마지막에 끝나는 놈을 쓰는게 유효한가? 다음 $(s, e)$에서 어차피 $e$는 꽤 크고, $s$가 빠른 놈이 들어오는게 문제인 것 같은데, 그러면 자유로운 친구가 더 오래 쉬도록 해야하는거 같다 .그러면 맞는거같다!! 셋같은걸로 지점을 잘 찾아보자. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pii> contests(N); rep(i, 0, N) cin >> contests[i].first >> contests[i].second; sort(all(contests), [](const pii &a, const pii &b){ if(a.second == b.second) return a.first < b.first; return a.second < b.second; }); int ans = 0; int T = 0; multiset<int> st; rep(i, 0, K-1) st.insert(0); for(auto &[a, b]: contests){ if(a <= T) continue; auto it = st.lower_bound(a); if(it == st.begin()){ ans++; T = b; continue; } it--; st.erase(it); st.insert(b); } cout << ans; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24945 🧐 관찰 및 접근 # 서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자. $N = 3$ 브루트포스에 가깝게 풀 수 있을 것 같다. 문자는 어차피 최대 3개 존재하므로, 3개에 대해 $X$가 가질 수 있는 경우의 수 $3^3$가지, $Y$가 가질 수 있는 경우 $3^3$가지를 전이하면서 다익스트라로 풀 수 있을 것 같다. ㅇㅋ 된당 $S_i = a$ 모든 문자가 a라면? $X$에 들어있는 문자 개수, $Y$에 들어있는 문자 개수 두가지를 이용해서 $N^2$ 정점 다익스트라가 가능해보인다. $N \leq 30$ 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데… 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다. 그럼 $Y$가 될 수 있는 경우의수는 $O(N^2)$이고 $X$를 만들때든, $Y$를 만들기위해 빌드업하고 있을때든 결국 $X$도 $X$의 substr로 존재해야한다. 이것도 경우의수가 $O(N^2)$ 인 것 같다. $Y$를 붙일 수 있는지 검사하는? 그런것들이 전처리를 안하면 $O(N)$쯤 되어보이니, 아마 종합해서 $O(N^5)$정도로 풀 수 있지 않나? 근데 DP 전이식이 헷갈린다. 이게 상호 참조가 없나? 비용들이 달라서 다익으로 해야될 것 같은데. $\text{DP}[x][y]$: 현재 $X$에 $x$, $Y$에 $y$가 들어있다고 하자. $A$ 연산을 거치면 $x$에 한개가 붙고, $y$는 그대로다. $B$ 연산을 거치면 $x$가 빈 문자열이 되고, $y$는 $x$의 값으로 갱신된다. $C$연산을 거치면 $x = x + y$가 되고, $y$는 그대로다. 아하, 생각보다 $y$가 갱신될일이 없다. 그리고 $y$가 갱신된다면 $x$가 빈 문자열이 된 상태에서 시작한다! 복사하고 붙여넣는 과정을 그냥 해버렸다고 생각하는게 더 쉬울 것 같다. $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자. 이건 $\text{DP}[i][j-1]$ 후 $A$연산을 하거나 어떤 $i \leq i', j' \leq j$가 있어서 그친구를 복사한 후 붙여넣기를 여러번 하거나. 이건 그리디하게 되는듯? 한번 짜보자. 오!!! 이걸로 대충 $30^5$정도는 성공했다! $N \leq 200$ 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데… 섭태 5는 세제곱, 섭태 6은 제곱로그겠다. 음, 위에서 했던 관찰대로 $Y$에 복사해서 넣으면 $X$는 초기화돼서 시작하므로, DP를 $B$연산으로 $Y$에 복사한거까지 했을 때를 기준으로 하자. 젤 중요한거는 저 그리디하게 비교하면서 뒤로 슝슝슝 가는 파트인 것 같다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> S >> A >> B >> C; if(N >= mxN) { cout << -1 << "\n"; return; } rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = LLONG_MAX; rep(i, 0, N+1) rep(j, i+1, N+1) DP[i][j] = A * (j-i) + B; const mint base = 131; const mint2 base2 = 137; vector<mint> hsh(N+1), pw(N+1); vector<mint2> hsh2(N+1), pw2(N+1); hsh[0] = 0; pw[0] = 1; hsh2[0] = 0; pw2[0] = 1; rep(i, 0, N){ hsh[i+1] = hsh[i] * base + S[i]; pw[i+1] = pw[i] * base; hsh2[i+1] = hsh2[i] * base2 + S[i]; pw2[i+1] = pw2[i] * base2; } auto getHash = [&](int l, int r) -> pair<ll, ll>{ ll ret1 = (hsh[r] - hsh[l] * pw[r-l]).get(); ll ret2 = (hsh2[r] - hsh2[l] * pw2[r-l]).get(); return {ret1, ret2}; }; ll ans = N*A; rep(L, 1, N+1){ // A 연산 앞뒤에 붙여서 전이할 때 if(L >= 2) rep(s, 0, N){ if(s+L > N) break; int e = s+L; DP[s][e] = min(DP[s][e], DP[s+1][e]+A); DP[s][e] = min(DP[s][e], DP[s][e-1]+A); } // 해당 문자열을 복사하는 최소 비용 map<pair<ll,ll>, vector<int>> mp; rep(s, 0, N){ if(s+L > N) break; int e = s+L; mp[getHash(s, e)].push_back(s); } // 복사 연산으로 전이 for(auto& [_, v]: mp){ int sz = v.size(); ll mn = 1e18; for(auto s: v) mn = min(mn, DP[s][s+L]); // 다음에 갈 수 있는 위치 vector<int> nxt(sz, sz); for(int i = 0, j = 0; i < sz; i++){ while(j < sz && v[j] < v[i]+L) j++; nxt[i] = j; } rep(i, 0, sz){ int s_pos = v[i]; int cidx = i; int cnt = 0; while(cidx < sz){ cnt++; int e_pos = v[cidx]+L; if(e_pos > N) break; DP[s_pos][e_pos] = min(DP[s_pos][e_pos], mn + (C * cnt) + ((e_pos - s_pos) - (L * cnt)) * A + B); cidx = nxt[cidx]; } } } } ans = min(ans, DP[0][N] - B); cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27844 번역 문제 번역 # $N$개의 목초지가 있고 ($2 \le N \le 2\cdot 10^5$), $N-1$개의 도로로 연결되어 트리를 형성합니다. 모든 도로를 건너는 데 1초가 걸립니다. 각 목초지는 처음에 풀이 0개이고, $i$번째 목초지의 풀은 초당 $a_i$ ($1\le a_i\le 10^8$) 단위의 속도로 자랍니다. Farmer John은 처음에 목초지 1에 있으며, 모든 목초지의 풀에 비료를 주기 위해 돌아다녀야 합니다. 그가 $x$ 단위의 풀이 있는 목초지를 방문하면, $x$만큼의 비료가 필요합니다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14464 🧐 관찰 및 접근 # 소에 대해서는 끝나는 시간이 가장 빠른 소를, 닭에 대해서는 가장 $T$가 빨리 오는 닭을 쓰는 그리디가 성립한다. 이를 구현하는 방법은 여러가지가 있겠지만, 여기서는 multiset과 이분탐색을 이용하겠다. 💻 풀이 # 코드 (C++): void solve(){ int C, N; cin >> C >> N; multiset<int> chicken; rep(i, 0, C){ int x; cin >> x; chicken.insert(x); } vector<pii> cow(N); rep(i, 0, N) cin >> cow[i].first >> cow[i].second; sort(all(cow), [](pii a, pii b){ return a.second < b.second; }); int ans = 0; for(auto [s, e]: cow){ auto it = chicken.lower_bound(s); if(it != chicken.end() && *it <= e){ ans++; chicken.erase(it); } } cout << ans << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31760 번역 문제 # Apolyanka와 Büdelsdorf는 최근 접촉하게 된 두 개의 작은 신석기 시대 마을입니다. $1$부터 $N$까지 번호가 매겨진 $N$개의 자원이 있으며, 각 마을은 서로 다른 효율성을 가지고 이들 자원을 독립적으로 생산할 수 있습니다. 자원 $i$를 한 단위 생산하기 위해, Apolyanka는 $A_i$ 인시(person-hours)가 필요하고, Büdelsdorf는 $B_i$ 인시가 필요합니다. 현재 Apolyanka는 주어진 각 시간 기간에 자원 $i$를 $U_i$ 단위 생산하고 있으며, Büdelsdorf는 $W_i$ 단위를 생산하고 있습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26969 번역 문제 번역 # Bessie는 “소 유전체학: 다큐멘터리"를 보고 싶지만, 혼자 가고 싶지 않습니다. 불행히도, 그녀의 친구들은 함께 갈 만큼 열정적이지 않습니다! 따라서 Bessie는 친구들이 영화관에 함께 가도록 뇌물을 줘야 합니다. 그녀는 두 가지 뇌물 수단을 가지고 있습니다: 무니(mooney)와 아이스크림 콘입니다.