📝 문제 정보 # 링크: 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/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) 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27421 번역 문제 # Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20929 🧐 관찰 및 접근 # 문제의 제한인 $2^{19}$와 횟수를 볼때, 이분 탐색을 장려하고 있는 것 같다. 다음과 같은 상황을 생각해보자. 길이 8의 배열 2개에서 다음과 같이 $N/2$번째 수인 4번째 수를 비교했을 때, 위와 같이 작은 배열의 아래 절반과 큰 배열의 윗쪽 절반은 고려할 필요가 없어진다. 위와 마찬가지로, 위에서 작은 배열 쪽 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) 🔒 구현 코드 잠금