Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5638 🧐 관찰 및 접근 # 댐에 수문이 있고, 유량과 피해비용이 있는 것 같다. 피해비용은 여는 시간에 비례하지 않는 것 같다. 그러면 각 수문에 대해, 유량에 시간을 곱해서 각 수문이 버릴 수 있는 물의 양을 구할 수 있고, 그에 따른 가격이 나온다. 이건 그리디하게는 조금 곤란하고, 배낭 문제로 되나? 했는데, $V$가 너무 크다! 그런데 수문의 개수가 $n \leq 20$으로 유의미하게 작다. 각 테스트케이스에 대해 모든 수문을 열어보는 경우의 수를 수행할 수 있을 것 같다. 시간복잡도 $O(2^n \cdot nm)$ 정도에 동작할 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pll> door(N); rep(i, 0, N) cin >> door[i].first >> door[i].second; int Q; cin >> Q; rep(q, 1, Q+1){ ll V, T; cin >> V >> T; ll ans = 1e18; rep(bit, 0, 1<<N){ ll wat = 0, cost = 0; rep(i, 0, N) if(bit & (1<<i)) wat += door[i].first*T, cost += door[i].second; if(wat >= V) ans = min(ans, cost); } cout << "Case " << q << ": "; if(ans == 1e18) cout << "IMPOSSIBLE\n"; else cout << ans << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1739 🧐 관찰 및 접근 # $(1, 1) \rightarrow (6, 6)$으로 가기 위해선 어때야 하지? $r_1, c_6$이 오른쪽 / 아래이거나, $c_1, r_6$이 아래 / 오른쪽이거나.. 오른쪽 / 아래를 참, 왼쪽/위를 거짓이라고 생각하면, $(r_1 \land c_6) \lor (r_6 \land c_1)$ 같은 느낌인가? 이걸 어떻게 잘 하면 2-sat으로 바꿀 수 있을것같은데.. $r6$이 아니라면, $r1, c6$이 참이어야하고, 이런 느낌으로 되는것같다. $(\neg r_6 \rightarrow r_1) \land (\neg r_6 \rightarrow c_6)$ 이런걸 4개에 대해서 하면 될거같은데? $(r_1, c_1) \rightarrow (r_2, c_2)$ 라고 해보자. 일단 $r_1 < r_2, c_1 < c_2$라고 하자. $(\neg r_1 \rightarrow r_2) \land (\neg r_1 \rightarrow c_1)$ $(\neg c_2 \rightarrow r_2) \land (\neg c_2 \rightarrow c_1)$ $(\neg r_2 \rightarrow r_1) \land (\neg r_2 \rightarrow c_2)$ $(\neg c_1 \rightarrow r_1) \land (\neg c_1 \rightarrow c_2)$ 이렇게 할 수 있을 것 같다. 그러면 $r_1 > r_2, c_1 > c_2$라면? 똑같이 $r_1, c_2$의 경로를 이용하거나, $r_2, c_1$의 경로를 이용해야하는건 같다. 그런데 왼쪽이라서 참이어야 하는게 아니라 목적지가 거짓이어야 한다. $(\neg r_1 \land \neg c_2) \lor (\neg r_2 \land \neg c_1)$ 처럼 되어야할 것 같다. 아하, 대소관계가 바뀌면 이게 낫으로 바뀐다. 이걸 이용해서 더 쉽게 구현이 될라나? 구현 실수하지 않게 조심하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; DirectedGraph tsat((N+M)*2); rep(i, 0, K){ int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; r1--; c1--; r2--; c2--; r1 *= 2; r2 *= 2; c1 = (c1 + N) * 2; c2 = (c2 + N) * 2; if(r1 == r2 && c1 == c2) continue; if(r1 == r2){ if(c1 < c2) tsat.add_edge(r1^1, r1); else tsat.add_edge(r1, r1^1); continue; } if(c1 == c2){ if(r1 < r2) tsat.add_edge(c1^1, c1); else tsat.add_edge(c1, c1^1); continue; } if(c1 > c2) r1^=1, r2^=1; if(r1 > r2) c1^=1, c2^=1; tsat.add_edge(c1^1, r1); tsat.add_edge(c1^1, c2); tsat.add_edge(r2^1, r1); tsat.add_edge(r2^1, c2); tsat.add_edge(r1^1, r2); tsat.add_edge(r1^1, c1); tsat.add_edge(c2^1, r2); tsat.add_edge(c2^1, c1); } cout << (tsat.is2SAT() ? "Yes\n" : "No\n"); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30880 🧐 관찰 및 접근 # 누가봐도 세그먼트트리 세팅인것같다. 금광같은거죠 노드 정의를 어떻게 하면 좋을까? 부분열이니까, R / O / C / K 개수는 당연히 있어야하고.. ROCK 개수는 ROCK개수 + 왼쪽 R + 오른쪽 OCK, RO + CK, ROC + K,, 아하, R / RO / ROC / ROCK / O / OC / OCK / C / CK / K 다 세면 되나? 아 그런데, ROCK의 개수를 세는게 아니라 ROCK로 끝나는 문자열의 개수를 세야한다는건, 길이도 어떻게 잘 곱해야되는것같은데 $XRRX$ 와 $XOCK$ 를 합친다고 생각해보자. 답은 $XRROCK, XROCK, XROCK, RROCK, ROCK, ROCK$로 6개인것 같다. 뒤에 $OCK$근처에서는 별 감흥이 없는 것 같고, 앞에있는 $R$들에 대해서만 상관이 있는 것 같다. 그 위치들에 대해, $2 + 4$ 해서 6이 나온 것 같다. 노드 안에서 $R$에 대해, $R$의 개수가 아니라 $R$로 끝나는 부분 문자열의 개수를 저장하는게 좋겠다. R, RO, ROC, ROCK에 대해서 그렇게 해주면 충분하다! 💻 풀이 # 코드 (C++): struct Node{ mint R = 0, RO = 0, ROC = 0, ROCK = 0, O = 0, OC = 0, OCK = 0, C = 0, CK = 0, K = 0; mint len = 0; mint ans = 0; Node(){}; Node(char c){ if(c == 'R') R += 1; if(c == 'O') O += 1; if(c == 'C') C += 1; if(c == 'K') K += 1; len = 1; }; }; Node pull(Node a, Node b){ Node ret; ret.R = a.R + mint(2).pow(a.len.val)*b.R; ret.O = a.O + b.O; ret.C = a.C + b.C; ret.K = a.K + b.K; ret.RO = a.RO + mint(2).pow(a.len.val)*b.RO + a.R*b.O; ret.OC = a.OC + b.OC + a.O*b.C; ret.CK = a.CK + b.CK + a.C*b.K; ret.ROC = a.ROC + mint(2).pow(a.len.val)*b.ROC + a.RO*b.C + a.R*b.OC; ret.OCK = a.OCK + b.OCK + a.OC*b.K + a.O*b.CK; ret.ROCK = a.ROCK + mint(2).pow(a.len.val)*b.ROCK + a.ROC*b.K + a.RO*b.CK + a.R*b.OCK; ret.len = a.len + b.len; return ret; } void solve(){ int N; cin >> N; string S; cin >> S; vector<Node> v(N); rep(i, 0, N) v[i] = Node(S[i]); SegmentTreeNode ST(N, v); int Q; cin >> Q; while(Q--){ int op; cin >> op; if(op == 1){ int idx; cin >> idx; char c; cin >> c; ST.set(idx-1, Node(c)); } else{ int l, r; cin >> l >> r; l--; r--; cout << ST.query(l, r).ROCK << '\n'; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30478 문제 # 러시아워입니다! 오늘 퇴근 후, 쇼핑몰이 닫기 전에 가족 모두에게 줄 사탕을 사야 합니다. 가족들은 독점성과 균일성을 매우 중요하게 여기기 때문에, 당신은 그들을 감동시키기 위한 계획을 세웠습니다. 각 가족 구성원에게 주는 사탕은 모두 단일 브랜드여야 하며, 동일한 브랜드의 사탕을 다른 가족 구성원이 받아서는 안 됩니다. 또한, 누군가를 더 사랑한다는 사실을 들키고 싶지 않기 때문에 모든 가족 구성원이 같은 수의 사탕을 받아야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14587 🧐 관찰 및 접근 # 전처리를 적당히 할 수 있을까? 이분탐색을 좀 하면서 밀면서 하면, 특정 도미노를 한쪽으로 밀었을때 어디까지 넘어가는지 할 수 있나? 아, min/max 세그먼트 트리로 되는거같다 마지막은 그리디가 아니라 DP로 해야한다! 아니근데 X가 정렬되어 주어지지 않는다;;;;; 그래도 구현이 막 어렵지 않은듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> X(N), H(N); vector<pll> dominos(N); rep(i, 0, N) cin >> dominos[i].first >> dominos[i].second; sort(all(dominos)); rep(i, 0, N){ X[i] = dominos[i].first; H[i] = dominos[i].second; } SegmentTreeMinMax ST_min(N), ST_max(N); // calc leftmost ST_min.set(0, 0); rep(i, 1, N){ ll val = X[i] - H[i]; auto idx = lower_bound(all(X), val) - X.begin(); auto Q = ST_min.query(idx, i-1); ST_min.set(i, min((ll)i, ST_min.query(idx, i-1).first)); } // calc rightmost ST_max.set(N-1, N-1); rrep(i, 0, N-1){ ll val = X[i] + H[i]; auto idx = upper_bound(all(X), val) - X.begin() - 1; auto Q = ST_min.query(i+1, idx); ST_max.set(i, max((ll)i, ST_max.query(i+1, idx).second)); } vector<int> DP(N, 1e9); DP[0] = 1; DP[ST_max.get_val(0)] = 1; rep(i, 1, N){ int lft = ST_min.get_val(i)-1; if(lft < 0) DP[i] = 1; else DP[i] = min(DP[i], DP[lft] + 1); int rht = ST_max.get_val(i); DP[rht] = min(DP[rht], DP[i-1] + 1); } cout << DP[N-1]; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11111 🧐 관찰 및 접근 # 대충봐도 격자그래프에서 MCMF같은데.. 덜끊어도 되니까 MaxFlow가 아닌가? 아하 뒤집으면 된다 아하, Flow 자체도 다 보내기 전이 최적일수도 있는것만 잊지 말자 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> costs = { {10, 8, 7, 5, 1}, {8, 6, 4, 3, 1}, {7, 4, 3, 2, 1}, {5, 3, 2, 2, 1}, {1, 1, 1, 1, 0} }; vector<vector<int>> board(N, vector<int>(M)); map<char, int> mp; mp['A'] = 0; mp['B'] = 1; mp['C'] = 2; mp['D'] = 3; mp['F'] = 4; rep(i, 0, N){ string S; cin >> S; rep(j, 0, M) board[i][j] = mp[S[j]]; } MinCostMaxFlow MCMF(N*M+2); MCMF.setST(N*M, N*M+1); vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; rep(i, 0, N) rep(j, 0, M){ if((i+j)%2){ MCMF.add(i*M+j, N*M+1, 1, 0); continue; } MCMF.add(N*M, i*M+j, 1, 0); rep(d, 0, 4){ int nx = i + dx[d], ny = j + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; MCMF.add(i*M + j, nx*M + ny, 1, -costs[board[i][j]][board[nx][ny]]); } } cout << max(0LL, -MCMF.match()); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/35108 🧐 관찰 및 접근 # $N$이 2500이니까 뭔가 제곱로그?까진 돌지 않을까 싶다. 음, 어떻게 잡으면 좋을지 모르겠지만, 저 주어진 게국지 그래프에서 안쪽의 네모중 왼쪽 위부터 반시계방향으로 $1, 2, 3, 4$ 라고 하면, $2, 4$번 정점을 기준으로 카운팅하고싶게 생기긴 했다. 일단 예제 그래프를 그려보자. ![[Drawing 2026-03-07 09.54.26.excalidraw.png]] 여기서 저 게국지모양을 찾아야 하는데… $1, 2, 3, 4$를 기7준으로 하면 $1, 2, 4$에 $5, 7, 6$을 붙이거나, $6, 7, 5$를 연결하는 두가지가 있겠다. 어.. 정점을 기준으로 세려고 하니 좀 까다로운거 같기도..? 그러면 간선을 기준으로..? 그러면 아무래도 양쪽에 날개가 붙어있는 간선으로 생각하자. 크아아아악 이래도 안되는데 일단 두 간선을 골라서 사이클을 고정시키는건 맞는거같다. 잉 이러면 걍 포함배제로 되는거 아닌가? 그러면 두 정점에 중복되는 정점, 세 정점에 중복되는 정점 뭐 그런게 필요한거같은데… 비트셋으로 하면 될라나? $O(M^2N/64)$ 정도인거같은데;; 일단 짜보자 좀 빡빡하다. 전처리를 잘 하면 시간 내로 들어간다. Clang이 훨 빠르네. 왜지? 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<pii> edges; vector<bitset<2500>> con(N); rep(i, 0, M){ int u, v; cin >> u >> v; u--; v--; edges.push_back({u, v}); con[u][v] = 1; con[v][u] = 1; } vector<ll> cnt1(N); rep(i, 0, N) cnt1[i] = con[i].count(); vector<vector<bitset<2500>>> con2(N, vector<bitset<2500>>(N)); rep(i, 0, N) rep(j, i+1, N) con2[i][j] = con2[j][i] = con[i]&con[j]; vector<vector<ll>> cnt2(N, vector<ll>(N)); rep(i, 0, N) rep(j, i+1, N) cnt2[i][j] = cnt2[j][i] = con2[i][j].count(); auto calc = [&](int v1, int v2, int v3, int v4) -> ll { auto &b1 = con[v1], &b2 = con[v2], &b3 = con[v3]; ll n1 = cnt1[v1] - (con[v1][v2] + con[v1][v3] + con[v1][v4]); ll n2 = cnt1[v2] - (con[v2][v1] + con[v2][v3] + con[v2][v4]); ll n3 = cnt1[v3] - (con[v3][v1] + con[v3][v2] + con[v3][v4]); ll n12 = cnt2[v1][v2] - (con2[v1][v2][v3] + con2[v1][v2][v4]); ll n23 = cnt2[v2][v3] - (con2[v2][v3][v1] + con2[v2][v3][v4]); ll n31 = cnt2[v3][v1] - (con2[v3][v1][v2] + con2[v3][v1][v4]); bitset<2500> b123 = b1&b2&b3; ll n123 = b123.count() - b123[v4]; return n1*n2*n3 - (n12*n3 + n23*n1 + n31*n2) + 2*n123; }; ll ans = 0; rep(i, 0, M) rep(j, i+1, M){ auto [a, b] = edges[i]; auto [c, d] = edges[j]; if(a == c || a == d || b == c || b == d) continue; if((!con[a][c] || !con[b][d]) && (!con[a][d] || !con[b][c])) continue; ll ret = 0; ret += calc(a, b, c, d); ret += calc(b, c, d, a); ret += calc(c, d, a, b); ret += calc(d, a, b, c); if(con[a][c] && con[b][d]) ans += ret; if(con[a][d] && con[b][c]) ans += ret; } cout << ans/2; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11493 🧐 관찰 및 접근 # 동전들을 swap해서 잘 옮겨서 맞춰야한다.. 일단 색을 모두 신경쓰긴 싫으니까, 1의 위치를 맞춘다고만 생각하자. 뭔가 이분그래프적으로 생각할 수 있지 않을까? 이게 움직이는것만 신경쓰면 플로이드워셜 + 이분그래프 매칭 최소비용…으로 하면 되는거같은데? 근데 swap이다보니 이렇게 맘대로 하는것보다 효율적인 방법이 무시될 것 같다. 일단 이분그래프로 생각을 좀 해보긴 하자. 그림을 그려보자. ![[Drawing 2026-03-07 15.31.09.excalidraw.png]] 그림 1의 예시이다. 어우 난잡해 ㅋㅋ 뭔가 증가경로 맛처럼 할 수 있는거같기는 한데.. ….가 아니라 그냥 이상태로 최소비용 최대유량 아닌가? 끝이네? 이분그래프로 분할할 필요도 없이, 그냥 유량으로 달리면 된다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; MinCostMaxFlow MCMF(N+2); MCMF.setST(0, N+1); rep(i, 0, M){ int u, v; cin >> u >> v; MCMF.add(u, v, 1e9, 1); MCMF.add(v, u, 1e9, 1); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(0, i, 1, 0); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(i, N+1, 1, 0); } cout << MCMF.match() << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23887 🧐 관찰 및 접근 # 설명을 대충 읽는데, BFS맛이 난다 허걱, 최대 학생이 25000명이라 나이브하게는 조금 곤란하긴 하다 근데 뭔가 트리처럼 해석할 수도 있을 것 같은데? MST인가? 아 근데 좀 유향 그래프? 맛인데… 위상정렬이네 이거 엥? 근데 이게 $2$번 학생이 $5, 6$번한테 받을 수 있다고해서 무조건 $5$번한테만 받는건 아니네? 그러면 다시 트리맛으로? 그러면 뭔가 트리의 지름을 최소화하는 느낌으로 가야하는 것 같은데… 그래프에서 가장 먼 두 점을 어떻게 구할 수 있을까? ???????? 아니 문제에서 $S$가 주어지는거였네 그러면 그냥 BFS를 돌리자 구현이 상당히 재밌다! 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; vector<vector<int>> board(N, vector<int>(M, 0)); vector<pii> students(K+1); vector<bool> visited(K+1); rep(i, 1, K+1){ int x, y; cin >> x >> y; x--; y--; students[i] = {x, y}; board[x][y] = i; } int S; cin >> S; set<int> Q; Q.insert(S); visited[S] = true; vector<vector<int>> links(K+1); vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1}; vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1}; while(!Q.empty()){ set<int> nQ; for(auto cur: Q){ auto [cx, cy] = students[cur]; rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == 0) continue; int nxt = board[nx][ny]; if(visited[nxt]) continue; visited[nxt] = true; links[cur].push_back(nxt); nQ.insert(nxt); } } swap(Q, nQ); } rep(i, 1, K+1) if(!visited[i]){ cout << -1; return; } vector<int> sz(K+1); function<void(int)> dfs = [&](int cur){ sz[cur] = 1; for(auto nxt: links[cur]){ dfs(nxt); sz[cur] += sz[nxt]; } }; dfs(S); rep(i, 1, K+1) cout << sz[i] << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/15309 🧐 관찰 및 접근 # 이진트리..는 아니고 삼각형이구나. 걍 좀 펴서 생각하면, 이항계수처럼 생각하면 되는 것 같다. $i$번째 줄은 $(Ax + B)^i$ 의 계수처럼 생각하면 되는듯? 아 근데 그 뭐냐 겹치게 하면 안되는구나 특정 삼각형은 그 초항만 생각하면 되는것같으니까, $m$개의 행을 포함하는 정삼각형을 어떻게 계산할지 생각해보자. 대충 로그정도에 계산하면 되는데.. 일단 초항이 1일때 식은 뭐랑 같지? $1 + (A+B) + (A^2 + AB + B^2) + \cdots$ 같은 느낌인건데… 어차피 행 자체에는 누적합 맛으로 할 수 있겠네. 어라? 이건 그냥 윗 행에다가 $A$를 곱하고, $B^N$만 더하면 될거같은딩. 대충 해버리죠? 아니 잠깐만!!!!!!!!! $m$이 $10^{18}$이다!! 비상!!!!!!!!! 로그가 붙을만한곳은 분할정복 거듭제곱같은거밖에 없는데… 아 잠깐만. 이거 그냥 그 유명한 고딩때 그 공식처럼 $(A-B)$곱하면 정리되는 꼴 아닌가? 그러면 $(A-B) + (A^2 - B^2) + (A^3 - B^3) + \cdots$ 이건 $(A + A^2 + \cdots + A^m) - (B + B^2 + \cdots + B^m)$이자나! $\frac{A^{m+1} - 1}{A-1} - \frac{B^{m+1} - 1}{B-1}$ 로 계산할 수 있을 것 같고, 이걸 $A-B$로 나눠서 끝내자. 아!! $A = B$인 경우를 조심해야할 것 같고, $A = 1$이나 $B = 1$인경우도 조심해야할 것 같다. $A = B$라면? $1 + 2A + 3A^2 + \cdots + mA^{m-1}$ 를 구해야하는데, 저 합을 $S$라고 하자. 그러면 $AS - S = 1 + A + A^2 + \cdots + A^m$ 니까, $A = 1$인 경우 말고는 이걸 구해서 $A-1$로 나누면 될 것 같은데? 케이스 처리를 조심하자. 💻 풀이 # 코드 (C++): void solve(){ mint A, B; cin >> A >> B; int Q; cin >> Q; while(Q--){ ll x, y, m; cin >> x >> y >> m; x--; y--; mint cho = 1; cho *= A.pow(x-y); cho *= B.pow(y); mint trig = 0; if(A == B){ if(A == 1) trig = mint(m)*(m+1)/2; else trig = (A.pow(m+1) - 1) / (A - 1).pow(2); } else{ if(A == 1) trig += m; else trig += (A.pow(m+1) - 1) / (A - 1) - 1; if(B == 1) trig -= m; else trig -= (B.pow(m+1) - 1) / (B - 1) - 1; trig /= (A-B); } cout << cho * trig << '\n'; } } 🔒 구현 코드 잠금