📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34609 번역 문제 # $1$번부터 $n$번까지 번호가 매겨진 $n$송이의 꽃이 왼쪽에서 오른쪽으로 일렬로 놓여 있다. 각 꽃은 백합(lily) 또는 장미(rose) 중 하나이다. $0$ 이상 $n$ 이하의 정수 $j$에 대해, $l_j$를 왼쪽 $j$개의 꽃 중 백합의 수, $r_j$를 오른쪽 $n - j$개의 꽃 중 장미의 수라 하자.
📝 문제 정보 # 링크: 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/1006 🧐 관찰 및 접근 # 유명한 통곡의 벽 문제 초라기 문제가 $2 \times N$의 원형이라 조금 곤란하다. 쉬운 경우부터 생각하자. $1 \times N$의 선형이라면, 계단 수처럼 DP로 풀 수 있을 것 같다. $2 \times N$의 선형이라도 DP로 가능한 것 같다. 두칸 전에서 오는 것에 대해 가로두개 / 위에 가로와 아래 따로 / 아래 가로와 위에 따로 한칸 전에서 오는 것에 대해 세로 / 위아래 따로 이 5가지 경우에서 가능한 것 같다! 그런데 원형이라 조금 곤란한데.. 뭔가 케이스를 나눌 수 있을 것 같긴 하다. 선형으로 생각했을때 맨 왼쪽에 대해, 그게 반대쪽과 이어진경우 / 안이어진경우. 위아래니까 각각 두가지, 총 4가지 경우의수를 따지면 될듯? 근데 이걸 어떻게 깔끔하게 코딩하지? 큰일났다. 둘다 반대쪽과 이어진 경우는 문제를 한칸 밀어서 풀기만 하면 되는 것 같은데, 한쪽만 밀린 경우가 까다롭다. 그런데 사실 모든 칸이 지그재그로 연결된 경우 빼고는 언젠가는 선형으로 풀어도 되는 타이밍이 있는 것 같다! 위에서 말한 타이밍은 예제에서는 $1-2, 10-11, 3-4, \cdots$로 연결된 느낌과 같다. 시간복잡도가 $O(NW)$이 되긴 하는데, 돌만하지 않을까? 저 지그재그만 예외처리를 해버리자. ㄲㅂ 시간초과네. 테케가 여러개라 그런 것 같다. 엥? 이거 그냥 길이를 $2N$으로 늘려서 하면 되지 않을까? …인줄알았는데 전이식 자체부터 두개 전에서 땡겨오다보니 차분트릭이 안먹히는것 같다. 전이식 자체에서도 여러칸 단위로 지그재그로 오면 할 수 있는게 없다.. DP에서, 상태공간을 조금 더 정의해보자. $\text{DP}[i][j]$라고 하면, i번째칸까지 봤을때 위아래 찬게 j상황이라고 생각해보자. $j = 0, 1, 2, 3$에서 위아래 모두 빔, 위 참, 아래 참, 위아래 모두 참과 같은 느낌이다. 이렇게해서 전이식을 잘 세우면 저 예외상황들을 처리하기 용이할 것 같다. 3번은 0번과 같으니 없애고, 나머지 3개로 정말 잘 처리해보자… 💻 풀이 # 코드 (C++): void solve(){ ll N, W; cin >> N >> W; vector<array<ll, 2>> v(N); rep(i, 0, N) cin >> v[i][0]; rep(i, 0, N) cin >> v[i][1]; auto calc = [&](bool con1, bool con2) { vector<array<ll, 3>> DP(N+1); // 0: 둘다끝, 1: 위가 튀어나감, 2: 아래가 튀어나감 rep(i, 0, N+1) rep(j, 0, 3) DP[i][j] = 1e18; DP[0][0] = 0; if(con1) DP[0][1] = 0; if(con2) DP[0][2] = 0; if(con1 && con2) DP[1][0] = 0; rep(i, 1, N+1){ DP[i][0] = min(DP[i][0], DP[i-1][0] + (v[i-1][0] + v[i-1][1] <= W ? 1 : 2)); DP[i][0] = min(DP[i][0], DP[i-1][1] + 1); DP[i][0] = min(DP[i][0], DP[i-1][2] + 1); if(i-2 >= 0 && v[i-2][0]+v[i-1][0] <= W && v[i-2][1]+v[i-1][1] <= W){ DP[i][0] = min(DP[i][0], DP[i-2][0] + 2); } DP[i][1] = min(DP[i][1], DP[i][0] + 1); if((i == N && con1) || (i < N && v[i-1][0] + v[i][0] <= W)){ DP[i][1] = min(DP[i][1], DP[i-1][0] + 2); DP[i][1] = min(DP[i][1], DP[i-1][2] + 1); } DP[i][2] = min(DP[i][2], DP[i][0] + 1); if((i == N && con2) || (i < N && v[i-1][1] + v[i][1] <= W)){ DP[i][2] = min(DP[i][2], DP[i-1][0] + 2); DP[i][2] = min(DP[i][2], DP[i-1][1] + 1); } } if(!con1 && !con2) return DP[N][0]; if(con1 && !con2) return DP[N-1][2] + 1; if(!con1 && con2) return DP[N-1][1] + 1; if(con1 && con2) return DP[N-1][0] + 2; }; auto origin = v; ll ans = 2*N; rep(con1, 0, 2) rep(con2, 0, 2){ if(con1 && v[0][0] + v[N-1][0] > W) continue; if(con2 && v[0][1] + v[N-1][1] > W) continue; ans = min(ans, calc(con1, con2)); } cout << ans << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5916 🧐 관찰 및 접근 # 트리가 주어진다. 두 정점 사이 경로에 1을 더한다. 두 정점 사이 경로의 가중치의 합을 계산한다. 나이브하게는 $O(QN)$이겠지만, HLD와 Lazy 세그먼트 트리를 이용해서 $O(Qlog^2N)$정도에 계산할 수 있을 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; Tree tree(N); rep(i, 0, N-1){ int u, v; cin >> u >> v; tree.add_edge(u, v); } tree.build(); LazySegmentTree seg(N+1); while(M--){ char op; cin >> op; int u, v; cin >> u >> v; if(op == 'P'){ vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) seg.update(L, R, 1); } else{ ll ans = 0; vector<pii> segs = tree.hld_path(u, v, false, false); for(auto [L, R]: segs) ans += seg.query(L, R); cout << ans << '\n'; } } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16964 🧐 관찰 및 접근 # dfs를 돌리듯이 지금까지 걸어온 과정들을 기록하면서 다음 노드를 갈 수 있었는가?를 체크하자. 💻 풀이 # 코드 (C++): import sys input = sys.stdin.readline N = int(input()) links = [set() for _ in range(N + 1)] for _ in range(N-1): a, b = map(int, input().split()) links[a].add(b) links[b].add(a) lst = list(map(int, input().split())) if lst[0] != 1: print(0) exit() nidx = 1 stk = [1] while nidx < N: if not stk: print(0) exit() cur = stk[-1] if lst[nidx] in links[cur]: stk.append(lst[nidx]) nidx += 1 else: stk.pop() print(1) 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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/35288 🧐 관찰 및 접근 # 문제를 정리하면 다음과 같다. 트리가 주어진다. 간선을 $K$개 지워서 포레스트로 만든다. 포레스트를 잘 합쳐서 트리의 지름이 최소가 되도록 하자. 포레스트를 잘 합치는 문제는 빌라봉으로 유명하다. 이 문제에 따르면, 세개 이상의 트리를 합칠 때, 가장 긴 트리의 지름 세개를 $a \geq b \geq c$ 라고 하면 그 결과는 $\max(a, \lceil\frac{a}{2}\rceil + \lceil\frac{b}{2}\rceil + 1, \lceil\frac{b}{2}\rceil + \lceil\frac{c}{2}\rceil + 2)$ 결과는 위와 같고, 이는 새로 만든 간선을 $0, 1, 2$개 이용하는 경로중 가장 긴것과 같다. 그리디하게 가장 긴 지름의 중심에 다른 중심들을 이은 모양에서 나온 결과이다. 그렇다면 트리를 빠르게 쪼개서 지름만 빠르게 계산할 수 있으면 되는 것 같다. 이걸 어떻게 할 수 있을까? 예제 1번의 트리를 ETT를 하면서 그려보자. ![[Drawing 2026-02-25 22.49.23.excalidraw.png]] 그리고 세번째 쿼리를 생각해보자. $(1, 2), (3, 6), (4, 5, 7)$으로 나뉘어야 하는디… ETT로 생각하면, $(1, 2, (5, (3, 6), 4, 7))$ 같은 느낌으로 그룹지어지는건가? 잘 처리된 부분들은 상관 없는데, $(5, 4, 7)$같은데서 지름을 어떻게 구하면 좋을지 감이 안온다. 일단 저걸 $(5), (4,7)$ 두 덩어리를 합치는 연산으로 보자. 오일러 투어 테크닉을 적용하면 연속 구간에 속하는 노드들의 지름은 세그먼트 트리로 구할 수 있다고 한다. 이걸 어떻게 하는거지? 트리 두개의 지름의 양끝 점을 각각 $(a, b), (c, d)$ 라고 할때 두 트리를 합친곳에서의 지름은 $(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)$중에서 존재한다. 이를 pull연산으로 잘 정의해보자. 구현이 상당히 어렵다.. 💻 풀이 # 코드 (C++): void solve(){ int N, Q; cin >> N >> Q; vector<vector<int>> links(N+1); vector<pii> edges; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); edges.push_back({u, v}); } auto [ETT_in, ETT_out] = ETT(N, links); vector<int> ETT_inv(N+1); rep(i, 1, N+1) ETT_inv[ETT_in[i]] = i; LCA_Tree = new Tree_LCA(N+1, links); vector<Node> nodes(N+1); rep(i, 1, N+1) nodes[i] = Node(ETT_inv[i], ETT_inv[i], 0); SegmentTreeNode seg(N+1, nodes); vector<int> edge_to_subtree(N-1); rep(i, 0, N-1){ auto [u, v] = edges[i]; if(LCA_Tree->depth[u] < LCA_Tree->depth[v]) swap(u, v); edge_to_subtree[i] = u; } while(Q--){ int K; cin >> K; vector<int> cuts(K); rep(i, 0, K) cin >> cuts[i]; vector<Node> Query_nodes; vector<pair<int, bool>> events; // {ETT_idx, is_end} for(auto c: cuts){ int u = edge_to_subtree[c-1]; events.push_back({ETT_in[u], false}); events.push_back({ETT_out[u], true}); } sort(all(events)); int cur = 1; stack<Node> stk; stk.push(Node()); for(auto [idx, is_end]: events){ if(is_end){ Node& top = stk.top(); top = seg.pull(top, seg.query(cur, idx)); cur = idx+1; Query_nodes.push_back(top); stk.pop(); } else{ Node& top = stk.top(); top = seg.pull(top, seg.query(cur, idx-1)); cur = idx; stk.push(Node()); } } Node& top = stk.top(); top = seg.pull(top, seg.query(cur, N)); Query_nodes.push_back(top); sort(all(Query_nodes), [](Node a, Node b){ return a.dist > b.dist; }); int ans = 0; if(Query_nodes.size() > 0) ans = Query_nodes[0].dist; if(Query_nodes.size() > 1) ans = max(ans, (Query_nodes[0].dist+1)/2 + (Query_nodes[1].dist+1)/2 + 1); if(Query_nodes.size() > 2) ans = max(ans, (Query_nodes[1].dist+1)/2 + (Query_nodes[2].dist+1)/2 + 2); cout << ans << "\n"; } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2803 🧐 관찰 및 접근 # 비트마스킹적으로 접근해보면, 여러 장난감 상자들의 or 연산결과가 $1111111..$이 되도록 하는 조합의 개수를 찾으면 되는 것 같다. $N$에 대해 생각하긴 까다로우므로, $M \leq 20$인 것을 이용해서 $M$에 대한 비트마스킹된 상자의 수로 생각해보자. 이후 과정을 포함배제로 진행하면 $O(2^N \times 2^N)$이겠지만, 우리는 SOS DP를 이용해서 $O(N2^N)$ 에 계산할 수 있음을 알 수 있다. 그런데 그냥 기본적인 SOS DP랑은 세팅이 조금 다른가? 고민해보자. 기본적인 SOS DP는 해당 비트마스크의 부분집합의 원소 개수의 합이다. 이번에 구해야하는건 해당 비트마스크를 만들어줄 수 있는 조합의 개수인데.. 결국 어떤 상자 $110011$을 골랐다고 생각해보자. 그러면, $??11??$ 인걸 모두 고르면 된다. 이걸 부분집합으로 세긴 힘들지만, 뒤집어서 생각한다면 $??00??$을 찾는 것이고, 이건 $110011$의 부분집합의 개수와 같은 것 같다! 자기 자신을 세지 않도록 조심하자. 그런데 저 방법으로 세면, 두개의 or연산밖에 고려하지 못한다… 3개 이상인걸 고려하려면 DP 설계를 조금 더 잘해야 할 것 같다. 아하, 원래게 $??11??$인 개수를 안다면, 여기에서 한개 이상만 고르면 된다. 그 개수를 $\text{cnt}$라고 하면, $2^{\text{cnt}} - 1$이 성립하는거 같기도? 근데 다시 생각해보니, 뭐랄까 원래가 $??10??$$ 인거랑 $??01??$$ 인거랑이 합쳐져서 되는것들을 못세는거..같기도? 연산해서 $11$을 만들기 위해선, $(11 + 10 + 01 + 00)^2$ 같은 느낌으로 생각해보자. 저 연산 결과는 $$ 11^2 + 10^2 + 01^2 + 00^2 + \\ 2(11\cdot10 + 11\cdot01 + 11\cdot00 + 10\cdot01 + 10\cdot00 + 01\cdot00) $$ 이고, 잘 고민해보니 $11$의 부분집합의 제곱 - $11, 01$의 부분집합의 제곱 - $00$의 부분집합의 제곱을 하면 깔끔하게 $11^2 + 2(11\times10 + 11\times01 + 11\times00 + 10\times01)$이 된다. 아니 잠깐만, 저 느낌을 그대로 가져가면 그냥 부분집합의 합으로 SOS DP를 한다음에 포함배제를 때려버리면 어떻게든 된다. 연산결과가 $11...11$인놈들 - $(01...11), (10..111)...$ + $...$ 이렇게 하면 되는구나! 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<int> A(N); rep(i, 0, N){ int K; cin >> K; int ret = 0; rep(j, 0, K){ int x; cin >> x; ret |= (1 << (x-1)); } A[i] = ret; } vector<int> SOS(1 << M, 0); for(auto x: A) SOS[x] += 1; rep(i, 0, M) rep(mask, 0, 1<<M) if(mask & (1 << i)) SOS[mask] += SOS[mask^(1<<i)]; mint ans = 0; rep(mask, 0, 1<<M){ int cnt = 0; rep(i, 0, M) if((mask & (1 << i)) == 0) cnt++; if(cnt & 1) ans -= (mint(2).pow(SOS[mask])); else ans += (mint(2).pow(SOS[mask])); } cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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/9345 🧐 관찰 및 접근 # 수열에서의 swap연산이 주어지고, 수열의 $L, R$ 범위가 주어졌을 때 해당 범위에 $L \leq x \leq R$의 모든 수가 있는지 묻는 문제이다. 합같은것으로는 저걸 구분할 수가 없다. $(3, 4)$나 $(2, 5)$나 같으니까. 아하, DVD들끼리 겹치지 않으므로 구간 최소/최댓값을 이용하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pii> a(N); rep(i, 0, N) a[i] = {i, i}; SegmentTree ST(N, a); while(K--){ int op, a, b; cin >> op >> a >> b; if(op == 0){ int aval = ST.query(a, a).first; int bval = ST.query(b, b).first; ST.set(a, bval); ST.set(b, aval); } else{ pii res = ST.query(a, b); if(res.first == a && res.second == b) cout << "YES\n"; else cout << "NO\n"; } } } 🔒 구현 코드 잠금