📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1734 🧐 관찰 및 접근 # 무향 그래프 $G = (V, E)$가 주어진다.
여기서 두가지 쿼리가 주어진다.
간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 각각 살펴보자. 먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4013 🧐 관찰 및 접근 # 그래프가 DAG라면 위상정렬을 하면서 DP를 진행할 수 있을텐데.. 같은 정점을 여러번 들릴 수 있으므로, 어떤 정점이 사이클 안에 들어있다면 해당 사이클 내의 ATM을 모두 들릴 수 있다! 서로 자유롭게 이동 가능한 관계라면 모두 자유롭게 들릴 수 있으므로, 이를 SCC로 묶어 DAG로 만들자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; DirectedGraph graph(N+1); rep(i, 0, M){ int u, v; cin >> u >> v; graph.add_edge(u, v); } DirectedGraph dag = graph.getCompressedGraph(); int sz = dag.V; vector<int> val(sz), DP(sz, -1e9), indeg(sz, 0); rep(i, 1, N+1){ int X; cin >> X; val[graph.sccId[i]] += X; } int S, P; cin >> S >> P; S = graph.sccId[S]; DP[S] = val[S]; rep(u, 0, sz) for(auto &v: dag.links[u]) indeg[v]++; queue<int> Q; rep(i, 0, sz) if(indeg[i] == 0) Q.push(i); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto nxt: dag.links[cur]){ DP[nxt] = max(DP[nxt], DP[cur] + val[nxt]); indeg[nxt]--; if(indeg[nxt] == 0) Q.push(nxt); } } int ans = 0; rep(i, 0, P){ int X; cin >> X; X = graph.sccId[X]; ans = max(ans, DP[X]); } cout << ans << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3648 🧐 관찰 및 접근 # 모든 심사위원에 대해 (and) 각 심사위원별로 표 두개중 하나를 만족해야 한다. (or) 따라서 $(A \lor B) \land (C \lor D) \land \cdots$ 의 2-sat 문제로 변환 가능하다! 모델링만 잘 해보자. 가능한 변수의 개수 $= 1000 *2 = 2000$ 에 대해 $i$ 번 참가자가 진출: $2*i$, 진출 실패: $2*i+1$로 모델링하자. 1번 참가자인 상근이는 무조건 통과해야 한다. $\neg x \to x$ 를 만족하면 되므로, $1 \to 0$을 추가하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; while(cin >> N >> M){ DirectedGraph dg(2*N); rep(i, 0, M){ int u, v; cin >> u >> v; if(u > 0) u = 2*(u-1); else u = 2*(-u-1)+1; if(v > 0) v = 2*(v-1); else v = 2*(-v-1)+1; dg.add_2sat_edge(u, v); } dg.add_2sat_edge(0, 0); cout << (dg.is2SAT() ? "yes\n" : "no\n"); } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16367
번역
문제 번역 # Mr. Dajuda는 TV 쇼 프로그램으로 유명한 사람으로, 가끔 시청자들에게 흥미로운 게임을 제안하고 상품을 상으로 제공합니다. 이번 주에 그가 제안한 게임은 다음과 같이 설명할 수 있습니다.
무대 위의 k개(k > 3)의 램프는 게임 시작 시 모두 꺼져 있습니다. 편의상 램프는 1부터 k까지 번호가 매겨져 있습니다. 각 램프는 빨간색 또는 파란색의 색상을 가지고 있습니다. 그러나 램프의 색상은 켜지기 전까지는 알 수 없습니다. 게임 참가자들은 무작위로 세 개의 램프를 선택하고 그 색상을 예측하도록 요청받습니다. 그런 다음 각 참가자는 선택한 램프의 예측된 색상이 기록된 종이를 게임 진행자인 Mr. Dajuda에게 제출합니다. 모든 램프가 켜지면 각 참가자는 자신이 예측한 색상 중 몇 개가 램프의 실제 색상과 일치하는지 확인합니다. 두 개 이상의 색상이 일치하면 상품을 받게 됩니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5214 🧐 관찰 및 접근 # 나이브하게 생각해볼까? 인접 리스트로 간선을 저장한다고 생각하면, $M\binom{K}{2} \approx MK^2$ 개의 정보가 저장된다. 그러면 BFS의 시간복잡도는 $O(V+E)$ 니까 조금 곤란한데… 잘 생각해보면, (1, 2, 3, 4), (2, 3, 4, 5) 하이퍼튜브가 있다고 가정하면, 겹치는 정보가 너무나도 많다! 첫 하이퍼튜브를 타고 2, 3, 4번 역에 1회만에 도착했다면, 두번째 하이퍼튜브에서 2, 3, 4번이 서로를 움직일 필요가 없다. 하이퍼튜브는 최대 1000개 존재한다. 또한 한 역은 최대 1000개의 하이퍼튜브에 속한다. 하이퍼튜브만 따로 정리해서, 그 안에서 움직이면 되지 않을까? 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> K >> M; rep(i, 0, M){ rep(j, 0, K){ int x; cin >> x; inhyper[x].push_back(i); hypertube[i].push_back(x); } } rep(i, 1, N+1) dist[i] = -1; dist[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int cur = q.front(); q.pop(); if(cur == N) break; for(int htube : inhyper[cur]){ for(int nxt : hypertube[htube]){ if(dist[nxt] == -1){ dist[nxt] = dist[cur] + 1; q.push(nxt); } } hypertube[htube].clear(); // 이미 방문한 하이퍼튜브는 볼일이 없다 } } cout << dist[N] << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34830 🧐 관찰 및 접근 # 문제 상황을 차근차근 살펴보자 $a, b$가 있을 때, $a - b$ 를 한번 지나가면 된다. $a, b, c$가 있을 때, $a - b, b- c, c-a$를 한번씩 지나가야한다. $a, b,c ,d$가 있을 때, $a-b, a-c, a-d, b-c, b-d, c-d$를 한번씩 지나가야 한다. 이를 그래프 이론으로 해석할 수 있지 않을까? 그래프가 있고, 각 간선을 한번씩 지나되, 시점과 종점이 달라도 된다 한붓그리기가 가능한가? 이제 이 문제는 오일러 경로를 가능하게 하는 문제로 바뀐다. 오일러 경로는, 홀수점이 두개 이하일때 가능하다. 정점이 $N$개 있다고 하면, 그래프는 완전그래프이므로 각 정점에 붙어있는 간선은 $N-1$개이다. $N$이 홀수라면, 모든 $N$개의 정점은 짝수점이다. $N$이 짝수라면, 모든 $N$개의 정점은 홀수점이다. 따라서, $N-2$개의 점들을 연결해서 홀수점이 2개가 되도록 만드는것이 최적이다. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; ll ans = N * (N-1) / 2; if(N%2 == 0) ans += N/2 - 1; cout << ans; }