이동식 저장소

오랜만에 코드포스에 참가했다. 온라인 대체과제니 조별과제니 스터디니 뭐니 해서 매우 바빠진 관계로 그동안은 간간히 백준 문제만 몇개 풀었는데, 그래도 Div. 3만큼은 놓칠 수 없다. Div. 2에서 2문제 풀면 레이팅 떨어지거든.. ㅠㅠ

다행히 11시 40분에 아슬아슬하게 퇴근해서 대회에 참여할 수 있었다.

A. Candies and Two Sisters

흔들리는 버스 안에서도 풀 수 있는 문제, $(n-1)/2$를 하면 된다. 

참 쉽죠?

B. Construct the String

문제에서 요구하는 내용은 언뜻 보면 어려워 보인다. 완전 탐색해야 하나? 생각했는데 사실 그럴 필요는 없고, 'a'부터 시작하여 b개의 알파벳을 계속 반복하면 된다. 다른 방법도 있겠지만 이게 가장 쉽고 빠르다.

C. Two Teams Composing

한 팀은 학생들의 능력이 모두 같게, 다른 한 팀은 능력이 모두 다르게 팀을 구성해야 한다. 이때 두 팀의 인원은 같아야 한다.

우선 (능력 $n$, 학생 수 $p$) 쌍을 모두 저장해 놓은 후, 팀을 만들어 보자. 그런데 예제에서도 볼 수 있듯이 능력이 4인 학생이 모두 한 팀에 속해야 하는 것은 아니며, 정답이 반드시 $p$ 중 하나가 아닐 수도 있다. 따라서 각 쌍에 대해 $[1,p]$에 속하는 모든 값을 검사해야 한다.

그런데 $n$이 최대 $200,000$이므로 선형 탐색으로는 시간 초과가 날 수 있다. 이분 탐색을 적용하여 $nlogn$ 시간에 정답을 구할 수 있다.

여담으로, 이분 탐색을 구현한 지 오래 돼서 잔실수가 있었다. 무려 3번이나..

D. Anti-Sudoku

완성된 스도쿠 답안이 주어질 때, 이것을 anti-sudoku로 바꿔 보자.

딱히 모르겠다. 브루트 포스를 해야 하나? 아니, 아니다. 대충 계산해봐도 시간 초과다. 그럼 어떻게 해야 하지?

...이렇게 시간 보내다가 자러 갔다. D번까지는 풀어볼 만 했는데..

C번까지는 평소보다 쉽게 풀었다. 사실 A, B번이 너무나도 쉬워서 4문제 정도는 풀어야 했는데, 못내 아쉽다.

이제는 열심히 공부해서 Div. 2를 노려 보자.