Algorithm

📝 문제 정보 # 링크: 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"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30208 🧐 관찰 및 접근 # 업무들의 순서때문에, 자유롭게 선택하지 못하는 경우들이 생긴다. 이게 어떤 느낌이지? ![[Drawing 2026-02-07 15.51.45.excalidraw.png]] 예제 입력 1의 순서는 다음과 같다. $1 \rightarrow 2 \rightarrow 3$을 보자. $1$까지 수행해서 중요도 $w_1$, 처리시간 $t_1$을 얻을 수 있다. $2$까지 수행해서 중요도 $w_1 + w_2$, 처리시간 $t_1 + t_2$를 얻을 수 있다. $3$까지 수행해서 $\cdots$ 저렇게 물건을 만들고 나면, 세개중에서 택1을 하는것 빼고는 배낭문제와 동일해진다. 트리 dfs로 냅색을 잘 돌면서 DP를 할 수 있을 것 같다. 근데 안에서 분기가 일어나면… 0이 아닌 모든 $p_i$들은 모두 다르다 라는 문장이 입력에 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int root, int w, int t){ w += W[cur]; t += T[cur]; bags[root].push_back({w, t}); for(auto nxt: links[cur]) dfs(nxt, root, w, t); } void solve(){ cin >> N >> S; rep(i, 1, N+1) cin >> W[i]; rep(i, 1, N+1) cin >> T[i]; rep(i, 1, N+1){ int p; cin >> p; links[p].push_back(i); } for(auto nxt: links[0]) dfs(nxt, nxt, 0, 0); rep(i, 0, N+2) rep(j, 0, S+1) KS[i][j] = 1e9; KS[0][0] = 0; rep(i, 0, N+1) rep(j, 0, S+1) { KS[i+1][j] = min(KS[i+1][j], KS[i][j]); for(auto [w, t]: bags[i]){ int nxt = min(S, j + w); // } KS[i+1][nxt] = min(KS[i+1][nxt], KS[i][j] + t); } } if(KS[N+1][S] == 1e9) cout << -1; else cout << KS[N+1][S]; } 🔒 구현 코드 잠금