Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10108 번역 문제 # 당신은 간식을 좋아하는 애완용 여우를 키우고 있습니다. 서로 다른 위치(데카르트 평면 위의 점으로 표현됨)에 N명의 이웃이 있으며, 각 이웃은 당신의 애완 여우에게 간식을 나눠줍니다. 각 이웃은 무제한으로 간식을 줄 수 있습니다. 원점(여우가 시작하는 위치)은 이 N개의 위치 중 하나가 아닙니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31740 🧐 관찰 및 접근 # 문제에서 주어진 그래프는 트리로 보인다. 트리에서는 모든 간선이 단절선이므로 하나만 잘라도 두 컴포넌트로 나뉘는것이 자명하다. 간선을 하나 자르고 나면 서브트리 하나와 나머지 부분으로 나뉜다. 서브트리의 가중치는 트리DP를 활용해 미리 계산해둘 수 있고, 나머지 부분은 전체 가중치 합에서 해당 서브트리의 가중치 합만큼을 빼면 된다. $O(N)$에 계산 가능해보인다. 💻 풀이 # 코드 (C++): int dfs(int c, int p){ par[c] = p; DP[c] = W[c]; for(auto nxt : links[c]){ if(nxt == p) continue; DP[c] += dfs(nxt, c); } return DP[c]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } rep(i, 1, N+1) cin >> W[i]; int SUM = dfs(1, -1); int ans = 2e9; pii ans2 = {-1, -1}; rep(i, 2, N+1) if(ans > abs(DP[i] - (SUM - DP[i]))){ ans = abs(DP[i] - (SUM - DP[i])); ans2 = {i, par[i]}; } cout << ans << '\n'; cout << ans2.first << ' ' << ans2.second << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2437 🧐 관찰 및 접근 # $1, 2, 4, 8, 16, \cdots$의 추로 모든 양의 정수를 측정할 수 있음이 자명하다. 이 이유를 살펴보면, $X$라는 무게의 추가 있을때, $X-1$까지의 모든 정수를 표현할 수 없다면 표현할 수 있는 최대치 + 1이 답이 된다. 추를 작은것부터 정렬해서, 빠지는 수 없이 무슨 양의 정수까지 최대한 잴 수 있는지 확인하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> v(N); rep(i, 0, N) cin >> v[i]; sort(all(v)); ll sum = 0; rep(i, 0, N){ if(v[i] > sum + 1){ cout << sum + 1 << "\n"; return; } sum += v[i]; } cout << sum + 1 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2138 🧐 관찰 및 접근 # 첫번째 / 마지막 전구를 제외하고는, 그리디하게 끄는 규칙이 가능하다. 첫번째 전구를 건드린 경우 / 안건드린 경우 두가지에 대해, 그리디하게 끄고 전체를 끌 수 있는지 확인하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; string S, T; cin >> S >> T; string ret = ""; rep(i, 0, N) ret += (S[i] == T[i] ? "0" : "1"); int ans = 1e9; // don't flip first string tmp = ret; int cnt = 0; rep(i, 1, N){ if(tmp[i-1] == '1'){ cnt++; tmp[i-1] = (tmp[i-1] == '1' ? '0' : '1'); tmp[i] = (tmp[i] == '1' ? '0' : '1'); if(i+1 < N) tmp[i+1] = (tmp[i+1] == '1' ? '0' : '1'); } } if(tmp[N-1] == '0') ans = min(ans, cnt); // flip first tmp = ret; cnt = 1; tmp[0] = (tmp[0] == '1' ? '0' : '1'); tmp[1] = (tmp[1] == '1' ? '0' : '1'); rep(i, 1, N){ if(tmp[i-1] == '1'){ cnt++; tmp[i-1] = (tmp[i-1] == '1' ? '0' : '1'); tmp[i] = (tmp[i] == '1' ? '0' : '1'); if(i+1 < N) tmp[i+1] = (tmp[i+1] == '1' ? '0' : '1'); } } if(tmp[N-1] == '0') ans = min(ans, cnt); if(ans == 1e9) ans = -1; cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14939 🧐 관찰 및 접근 # 맨 윗줄을 어찌저찌 일처리를 끝냈다고 가정하자. 두번째 줄부터, 그 윗줄의 남은 전구를 끄는 방법은 해당 칸 아래의 스위치를 컨트롤 하는 방법이 유일하다. 이를 사용하면 맨 윗줄을 처리할 수 있는 방법 $= 2^{10} = 1024$가지에 대해 해볼 수 있고, 시뮬레이션은 $100 \times 100 = 10000$번으로 충분히 시간 내로 들어온다. 맨 아랫줄에 켜진 전구가 남아있으면 안됨에 유의한다. 💻 풀이 # 코드 (C++): void solve(){ vector<string> board(10); rep(i, 0, 10) cin >> board[i]; int answer = 1e9; rep(bit, 0, 1<<10){ vector<string> cboard = board; int cnt = 0; auto press = [&](int r, int c){ cnt++; cboard[r][c] = (cboard[r][c] == 'O' ? 'X' : 'O'); if(r > 0) cboard[r-1][c] = (cboard[r-1][c] == 'O' ? 'X' : 'O'); if(r < 9) cboard[r+1][c] = (cboard[r+1][c] == 'O' ? 'X' : 'O'); if(c > 0) cboard[r][c-1] = (cboard[r][c-1] == 'O' ? 'X' : 'O'); if(c < 9) cboard[r][c+1] = (cboard[r][c+1] == 'O' ? 'X' : 'O'); }; rep(c, 0, 10) if(bit & (1 << c)) press(0, c); rep(r, 1, 10) rep(c, 0, 10) if(cboard[r-1][c] == 'O') press(r, c); bool ok = true; rep(c, 0, 10) if(cboard[9][c] == 'O') ok = false; if(ok) answer = min(answer, cnt); } if(answer == 1e9) cout << -1 << '\n'; else cout << answer << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14464 🧐 관찰 및 접근 # 소에 대해서는 끝나는 시간이 가장 빠른 소를, 닭에 대해서는 가장 $T$가 빨리 오는 닭을 쓰는 그리디가 성립한다. 이를 구현하는 방법은 여러가지가 있겠지만, 여기서는 multiset과 이분탐색을 이용하겠다. 💻 풀이 # 코드 (C++): void solve(){ int C, N; cin >> C >> N; multiset<int> chicken; rep(i, 0, C){ int x; cin >> x; chicken.insert(x); } vector<pii> cow(N); rep(i, 0, N) cin >> cow[i].first >> cow[i].second; sort(all(cow), [](pii a, pii b){ return a.second < b.second; }); int ans = 0; for(auto [s, e]: cow){ auto it = chicken.lower_bound(s); if(it != chicken.end() && *it <= e){ ans++; chicken.erase(it); } } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1149 🧐 관찰 및 접근 # 현재 집 $i$번의 색을 선택하기 위해 알아야 하는 정보는 $i-1$번째 집의 색이다. 따라서 $\text{DP}[i][j]$를 $i$번째 칠했을 때, 집의 색이 $j$인 경우 (빨, 초, 파)로 정의하면 점화식은 다음과 같다. $\text{DP}[i][j] = min_{c \neq j}{\text{DP}[i-1][c] +\text{cost}[i][j]}$ 💻 풀이 # 코드 (C++): void solve(){ cin >> N; rep(i, 0, N) rep(j, 0, 3) cin >> cost[i][j]; rep(i, 1, N+1) rep(j, 0, 3) DP[i][j] = 1e18; rep(i, 0, N) rep(cur, 0, 3) rep(nxt, 0, 3) if(cur != nxt) DP[i+1][nxt] = min(DP[i+1][nxt], DP[i][cur] + cost[i][nxt]); cout << min({DP[N][0], DP[N][1], DP[N][2]}); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11066 🧐 관찰 및 접근 # 파일 $C_i, C_{i+1}, \cdots, C_{j}$를 합치고 싶다고 하자. 이때, 해당 값은 $\text{DP}[i][j] = min_{i \leq k < j}(\text{DP}[i][k] + \text{DP}[k+1][j])$이 성립한다. 이는 $O(N^3)$이므로 충분히 돈다. 이런 문제는 top-down 재귀 DP로 구현하면 조금 더 편하게 짤 수 있다. TMI) 크누스 최적화를 이용해 더 빠르게도 풀 수 있다! 💻 풀이 # 코드 (C++): ll calc(int L, int R){ if(L == R) return 0; ll &ret = DP[L][R]; if(ret != -1) return ret; ret = LLONG_MAX; rep(k, L, R) ret = min(ret, calc(L, k) + calc(k+1, R) + (pfsum[R] - pfsum[L-1])); return ret; } void solve(){ cin >> N; rep(i, 1, N+1) cin >> C[i]; rep(i, 1, N+1) pfsum[i] = pfsum[i-1] + C[i]; rep(i, 1, N+1) rep(j, 1, N+1) DP[i][j] = -1; cout << calc(1, N) << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11000 🧐 관찰 및 접근 # 각 강의를 선분이라고 생각하면, 선분이 가장 많이 겹쳐진 타이밍이 가장 많은 강의실을 필요로 하는 타이밍일 것이다. 스위핑을 사용해서 이를 계산하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pair<int, bool>> events; // {time, isStart} rep(i, 0, N){ events.push_back({s, true}); events.push_back({e, false}); } sort(all(events)); int ans = 0, cnt = 0; for(auto [time, isStart]: events){ if(isStart) cnt++; else cnt--; ans = max(ans, cnt); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31498 🧐 관찰 및 접근 # 집 - 토카 - 돌돌이 형태로 있는 것 같다. 매 수행마다 토카는 $B, B-K, B-2*K \cdots$ 만큼 움직이고, 돌돌이는 $D$만큼 계속 움직인다. 토카가 잡힌다면, 그 순간 토카가 움직인 길이는 $D$보다 작을 것이다. 따라서 토카가 어느 순간 잡혔다면, 토카와 돌돌이가 계속 움직인다고 가정하면 돌돌이는 토카보다 훨씬 왼쪽에 있게 된다. 따라서 시간에 토카와 돌돌이의 위치에 단조성이 존재한다. 이분 탐색을 이용할 수 있겠다. 토카가 집에 도착하지도 못하는 상황, $K$가 0인상황 등 여러가지 예외 상황을 조심하자. 💻 풀이 # 코드 (python): A, B = map(int, input().split()) C, D = map(int, input().split()) K = int(input()) # 토카가 집에 도착할 수는 있는가? # B + (B-K) + (B-2K) + ... >= A if K > 0: # K = 0이면 무조건 도착할 수 있음 cnt = B // K # B - cnt * K >= 0 인 최대 cnt tot = B * (cnt + 1) - K * (cnt * (cnt + 1)) // 2 # B + (B-K) + ... + (B - cnt * K) if tot < A: print(-1) exit(0) # 토카가 집에 도착하는 타이밍이 돌돌이보다 이른가? def toka_move(time): if K > 0: time = min(time, B // K + 1) return B * time - K * (time * (time - 1)) // 2 ok, ng = 10**12, 0 # 토카가 집에 도착하는 가장 빠른 타이밍 while ok - ng > 1: mid = (ok + ng) // 2 if toka_move(mid) >= A: ok = mid else: ng = mid if D*ok < A + C: # 아직 돌돌이가 도착하지 않았다면 print(ok) else: print(-1) 🔒 구현 코드 잠금