Brute_force

📝 문제 정보 # 링크: 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/33527 🧐 관찰 및 접근 # 뭔가 전반적으로 세팅이 BOJ 5214 환승이 생각나는 것 같기도? 나이브하게 돈다면, 각 노선에 있을 수 있는 최대 정류장 수가 10만개니까, 이걸 다 돌기 시작하면 상당히 막막해진다. 그림을 그려서 어떤 상황인지 더 잘 판단해보자. ![[Drawing 2026-02-17 14.06.51.excalidraw.png]] 일단 예제 1번은 이런데, 흠. 확실히 정류장보단 노선 단위로 어떻게 잘 보고싶긴 하다. 노선은 총 $5 \times X = 500$개이다. 이때, 노선의 환승 각 정류장 $N$개마다 $\binom{5}{2}$ 개이므로 최대 $100\,000 \times = 1\,000\,000$개인 것 같다. 중복도 제거할수도 있고. 아? 이게 노선이 충분히 적으니, 플로이드 워셜이 가능해보인다. 쿼리는 정점에 대해 들어오니, $U_i, V_i$가 각각 5개 노선에 속하는 경우 25가지에 대해 노선으로 계산하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, X; cin >> N >> X; vector<array<int, 5>> bus(N); rep(i, 0, N) rep(j, 0, 5) cin >> bus[i][j]; auto toIdx = [&](pii p){ return p.first*X + (p.second - 1); }; vector<vector<int>> dist(5*X, vector<int>(5*X, 1e9)); rep(i, 0, 5*X) dist[i][i] = 0; rep(i, 0, N) rep(j, 0, 5) rep(k, j+1, 5){ int u = toIdx({j, bus[i][j]}), v = toIdx({k, bus[i][k]}); dist[u][v] = dist[v][u] = 1; } rep(k, 0, 5*X) rep(i, 0, 5*X) rep(j, 0, 5*X) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; int ans = 1e9; rep(i, 0, 5) rep(j, 0, 5){ int idx_u = toIdx({i, bus[u-1][i]}), idx_v = toIdx({j, bus[v-1][j]}); ans = min(ans, dist[idx_u][idx_v]); } cout << (ans == 1e9 ? -1 : ans+1) << "\n"; } } 🔒 구현 코드 잠금

w## 📝 문제 정보 링크: https://www.acmicpc.net/problem/10044 번역 문제 # JOI 군은 점심으로 중화요리집에서 샤오롱바오를 먹기로 했다. 샤오롱바오는 속재료와 뜨거운 국물을 밀가루 피로 싼 요리로, 먹을 때 국물이 주위로 튀는 것으로 알려져 있다. JOI 군이 주문한 샤오롱바오 세트는 속재료나 국물이 다른 N개의 샤오롱바오로 이루어져 있다. N개의 샤오롱바오는 등간격으로 일렬로 놓여 있으며, 순서대로 1부터 N까지 번호가 매겨져 있다. i번째 샤오롱바오와 j번째 샤오롱바오 사이의 거리는 절댓값 |i - j|이다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/7008 번역 문제 # Alice Catherine Morris와 그녀의 여동생 Irene Barbara는 자주 이메일을 주고받습니다. 항상 도청을 경계하며 통신 내용을 비밀로 유지하고자, 그들은 메시지를 두 단계로 암호화합니다. 모든 비알파벳 문자를 제거하고 모든 문자를 대문자로 변환한 후: 각 문자를 알파벳에서 s 위치 뒤의 문자로 치환합니다 (1 <= s <= 25) - 이를 s만큼의 시프트라고 합니다. 단계 1의 결과를 m개의 문자로 된 그룹으로 나누고 각 그룹의 문자들을 역순으로 배열합니다 (5 <= m <= 20). 메시지의 길이가 m으로 나누어떨어지지 않으면, 마지막 k개(m보다 작은)의 문자들을 역순으로 배열합니다. 예를 들어, s = 2이고 m = 6이라고 가정합시다. 평문이 “Meet me in St. Louis, Louis.“라면, 불필요한 문자를 제거하고 대문자로 변경하면: