Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27421 번역 문제 # Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20929 🧐 관찰 및 접근 # 문제의 제한인 $2^{19}$와 횟수를 볼때, 이분 탐색을 장려하고 있는 것 같다. 다음과 같은 상황을 생각해보자. ![[Drawing 2026-02-10 14.25.24.excalidraw.png]] 길이 8의 배열 2개에서 다음과 같이 $N/2$번째 수인 4번째 수를 비교했을 때, 위와 같이 작은 배열의 아래 절반과 큰 배열의 윗쪽 절반은 고려할 필요가 없어진다. ![[Drawing 2026-02-10 14.31.00.excalidraw.png]] 위와 마찬가지로, 위에서 작은 배열 쪽 4개를 제외하고 보면 $N$이 절반으로 줄어든 상황에서 같은 방식으로 반복할 수 있음을 알 수 있다. 따라서 위와 같은 과정을 1개가 남을때까지 반복하면 두 값은 각각 $N, N+1$번째 값일 것이다. 문제에서는 $N$번째 수를 요구했으므로, 더 작은 수를 출력하자. 💻 풀이 # 코드 (python): def Query(s, idx): """ 질문 "? s idx"을 하고 입력받는 함수 """ print("?", s, idx) return int(input()) N = int(input()) A_Lidx = 1 A_Ridx = N # [A_Lidx ~ A_Ridx] 에 정답 후보가 있음 B_Lidx = 1 B_Ridx = N # [B_Lidx ~ B_Ridx] 에 정답 후보가 있음 while A_Ridx > A_Lidx: A_mid = (A_Lidx + A_Ridx) // 2 B_mid = (B_Lidx + B_Ridx) // 2 A_ret = Query("A", A_mid) B_ret = Query("B", B_mid) if A_ret <= B_ret: A_Lidx = A_mid + 1 B_Ridx = B_mid else: A_Ridx = A_mid B_Lidx = B_mid + 1 A_ret = Query("A", A_Lidx) B_ret = Query("B", B_Lidx) print("!", min(A_ret, B_ret)) 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18214 번역 문제 번역 # Susan은 식탁 정리는 잘하지만, 사무실 책상 정리는 잘 못합니다. Susan은 방금 일련의 문서들에 대한 서류 작업을 마쳤고, 문서들은 여전히 책상에 쌓여 있습니다. 문서들은 일련번호가 있으며, 상사가 가져왔을 때는 순서대로 쌓여 있었습니다. 그러나 지금은 순서가 완벽하지 않은데, Susan이 너무 게을러서 더미에서 빠져나온 문서들을 제자리에 다시 넣지 않았기 때문입니다. 작업이 끝났다는 소식을 듣고, 상사는 그녀에게 보내고 있는 문서 상자에 문서들을 즉시 반납하기를 원합니다. 물론 문서들은 일련번호 순서대로 상자에 보관되어야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1300 🧐 관찰 및 접근 # 나이브하게 계산한다면, 정수가 $10^{10}$개 있으니 아무것도 안된다. 심지어 저장도 불가능하다. 어떤 수 $X$가 주어질 때, $X$보다 작거나 같은 수가 몇개인지는 $O(N)$에 셀 수 있다. 그리고 $X$보다 작거나 같은 수가 $K$개 이상인 수중 가장 작은 $X$가 정답이다. 따라서 파라메트릭 서치를 이용해 $O(N\log{10^9})$정도에 계산하자. 💻 풀이 # 코드 (python): N = int(input()) K = int(input()) def count(X): # 배열에서 X 이하 수의 개수 result = 0 for i in range(1, N+1): result += min(N, X // i) return result ok = N*N ng = 0 # 답의 범위는 [1, N*N]이므로 while ok - ng > 1: mid = (ok + ng) // 2 if count(mid) >= K: ok = mid else: ng = mid print(ok) 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 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)와 아이스크림 콘입니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/13448 🧐 관찰 및 접근 # 얻는 점수가 $M_i - t * p_i$가 아닌 $M_i$라면, 단순한 배낭문제일텐데.. 이걸 위해서 $N$에 대한 비트마스킹을 추가하는건 미친짓이다 그런데, 어떤 문제들을 풀기로 결정했다면, 그 문제들에 대해 순서를 정하는건 그리디하게 되지 않나? 문제 $i, j$가 있다고 하자. $i \rightarrow j$로 풀면 $(M_i - t * P_i) + (M_j - (t + R_i)*P_j)$ 점을 얻게 되고 $j -> i$로 풀면 $(M_j - t*P_j) + (M_i - (t + R_j) * P_i)$ 점을 얻게 된다. 위에서 아래 식을 빼면 $P_i * R_j - P_j * R_i$ 이고, $i \rightarrow j$가 이득이기 위해선 이게 양수여야하므로 $\frac{P_i}{R_i} \geq \frac{P_j}{R_j}$로 정렬하는 그리디 전략이 유효하다. 그렇다면 이 순서로 냅색 DP를 수행하자. 💻 풀이 # 코드 (C++): void solve(){ int N, T; cin >> N >> T; vector<Problem> Prob(N); rep(i, 0, N) cin >> Prob[i].M; rep(i, 0, N) cin >> Prob[i].P; rep(i, 0, N) cin >> Prob[i].R; sort(all(Prob), [](Problem &A, Problem &B){ return A.P * B.R > B.P * A.R; }); vector<ll> DP(T+1); for(auto [M, P, R]: Prob) rrep(t, 0, T+1){ if(t - R < 0) break; DP[t] = max(DP[t], DP[t - R] + (M - P*t)); } ll ans = 0; rep(i, 0, T+1) ans = max(ans, DP[i]); cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31265 🧐 관찰 및 접근 # 이해가 조금 어려운데, 결국 $N$개의 훈련 상황에서 $d$개의 훈련 가운데 하나를 계속 고르고, 훈련 시간의 합을 최대화 하고싶다. 배낭 문제와 비슷해보인다. $d$개의 선택지가 $N$번 주어지고, 훈련시간 = 무게의 합을 최대화 해야한다. 어? 나이브하게 하면 터지나? 각 단계마다 해야하는 연산량은 $M * d_i$이다. 총 연산량은 $\sum\limits_{i = 1}^N M * d_i \leq 1000 M$ 이니 괜찮을 것 같다. 아니!!!!!!!! 왜틀렸나 했네 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다. 한 훈련을 여러번 쓰지 않게 $M$에 대해 역순으로 돌면서, 잘 처리하자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N){ cin >> D[i]; tv[i].resize(D[i]); } rep(i, 0, N) rep(j, 0, D[i]) cin >> tv[i][j]; knapsack[0][0] = true; rep(i, 1, N+1) for(auto t: tv[i-1]) rrep(j, 0, M+1) if(j - t >= 0 && (knapsack[i-1][j-t] || knapsack[i][j-t])) knapsack[i][j] = true; rrep(j, 0, M+1) if(knapsack[N][j]){ cout << j; return; } cout << -1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30788 🧐 관찰 및 접근 # 대칭이동을 어떻게 수학적으로 표현할 수 있을까?? 쉬운거부터 해보자. 원래 점이 $(x, y)$에 있었다면 $90\degree$ 직선에 대칭시키면 $(-x, y)$ $45\degree$ 직선에 대칭시키면 $(y, x)$ $60\degree$ 직선에 대칭시키면 $y = \sqrt{3}x$에 대칭인거니까… 아니 이거 너무 까다로운데? 행렬연산은 하기 싫은데.. 각도를 기준으로 생각해보는것도 좋겠다. 극좌표계처럼, 원래 점이 $0\degree$에 있었다면 $60\degree$에 대해 대칭시키면 $120\degree$에 $120\degree$에 대해 대칭시키면 $240\degree$에 이런 느낌인 것 같다. 그렇다면 예제 1번은 $0\degree \rightarrow 120\degree \rightarrow 330 \degree \rightarrow 60 \degree \rightarrow 0$ 인거 같다! $45\degree = 225\degree$라고 생각하고, 가까운 곳을 찾아서 두배로 넘기고, 360으로 모듈러를 취하자. 자, 이제 한번씩 써서 0도로 돌아오는걸 어떻게 만들지? $15\degree$로 만들 수 있는건 $30\degree$ $x\degree$를 $a$에 대칭이동시키면 $(2a - x) \degree$가 되는 것 같다! 이걸 또 $b$에 대칭이동시키면 $(2b - (2a - x))\degree$ 인거같고.. 그러면 플마로 바뀌어가면서 더해지니까 결국 모듈러 360에 대해 두 그룹으로 나눈 합을 일정하게 맞출 수 있는지에 대한 문제로 바뀐다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; if(N%2){ cout << "NO"; return; } int sum = 0; for(auto x: A) sum += x; sum %= 360; DP[0][0][0] = true; rep(i, 0, N) rrep(j, 0, N) rep(k, 0, 360) if(DP[i][j][k]){ int nxt = (k + A[i]*2) % 360; DP[i+1][j+1][nxt] = true; DP[i+1][j][k] = true; } if(DP[N][N/2][sum] || DP[N][N/2][(sum + 180) % 360]){ cout << "YES\n"; vector<bool> used(N); int ci = N, cj = N/2, cs = sum; if(!DP[N][N/2][sum]) cs = (sum + 180) % 360; while(cj){ int prv = (cs - A[ci-1]*2) % 360; if(prv < 0) prv += 360; if(DP[ci-1][cj - 1][prv]){ used[ci-1] = true; ci--; cj--; cs = prv; } else ci--; } vector<int> v1, v2; rep(i, 0, N){ if(used[i]) v1.push_back(i+1); else v2.push_back(i+1); } rep(i, 0, N/2){ cout << v1[i] << ' ' << v2[i] << ' '; } } else cout << "NO"; } 🔒 구현 코드 잠금