티스토리 뷰

코드포스 GYM 링크


B. Colored Blanket


이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다.

담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다.


  1. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$
  2. 가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$


위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다.


코드 보기


C. Component Tree


전형적인 자료구조 문제다. 트리를 inorder로 방문하면서 새로 번호를 매기면, 하나의 서브트리를 연속한 수의 범위로 나타낼 수 있다. 이를 이용해서 top-down 방식의 indexed tree나 segment tree를 사용하면 된다. 가능한 속성이 매우 많을 수 있으므로, 트리의 각 노드에 속성마다 정보를 담고 있어야한다. 이는 STL map container를 사용하면 공간복잡도에 무리가 없다.


이 문제는 쿼리에 대해 바로 답을 출력하고 flush 해야만 다음 입력이 들어오는 대화형(communicate) 문제라는 것에 주의하자.


코드 보기


D. Data Center


문제에서 요구하는 구매해야하는 서버의 최소 개수는 쉽게 구할 수 있다. 용량이 많은 것 부터 사면서 총 용량이 $M$이상을 만족하는 순간을 계산하면 된다. 이제 구매해야하는 서버 개수 $K$를 알았다. $V_i \in \{0, 1\}$이므로 $V_i = 1$인 서버를 가장 많이 구매하면 된다. $V_i = 1$인 서버를 $x$개 샀을 때, $V_i = 0$인 서버를 $K-x$개 사는 것이므로, 각 서버 종류마다 가장 용량이 많은 서버 상위 $x$개와 $K-x$개의 용량을 합한 값이 $M$ 이상인지 매번 확인해주면 된다.


코드 보기


E. Election of Mayor


선거구를 합칠 때 현재 시장이 이득을 보는 경우는 아래 두 가지 뿐이다.


  1. 자신이 이긴 선거구와 자신이 진 선거구를 합쳐 이기는 경우
  2. 자신이 진 선거구 두 개를 합쳐 지는 경우


살펴보면 두 가지 경우 모두, 전체적으로 자신이 지는 선거구 하나를 없애는 똑같은 효과를 보인다. 따라서, 최소 몇 개의 선거구를 합쳐야 최종적으로 전체 선거를 이기는지 바로 계산할 수 있다. 이제 실제로 선거구들의 득표 현황을 봤을 때 그것이 가능한지 확인하고, 가능하다면 어떤 선거구들을 합칠지 출력한다.


코드 보기


F. Ilya Muromets


연속한 $K$개의 목을 자를 수 있다. 두 번의 칼질을 할 수 있다. P[i] = 1~i까지 목들이 있을 때 한 번의 칼질로 얻을 수 있는 최대 값이라고 정의하고, Q[i] = i~N까지 목들이 있을 때 한 번의 칼질로 얻을 수 있는 최대 값이라고 정의하자. 그러면 답은 P[i]+Q[i+1] (for 0 ≤ i ≤ N)이 된다.


코드 보기


G. FacePalm Accounting


크기가 $K$인 연속한 구간을 왼쪽부터 본다. 어떤 구간의 합이 음이 아닌 정수라고 하자. 그러면 그 구간 내에서 가장 오른쪽 값부터 감소 시키는 것이 전체적으로 좋음을 알 수 있다. 이를 이용해 오른쪽 부터 값을 감소시킨다. 그러면 총 시간복잡도 $O(N)$만에 문제를 해결할 수 있다.


코드 보기


I. Sale in GameStore


게임들을 가격이 싼 순서대로 정렬한 뒤, 가장 비싼 게임의 비용보다 같거나 작을 때 까지 살 수 있다. 주의해야할 것은 $N=1$인 경우 답이 2가 나오지 않게 조심한다.


코드 보기


K. Treeland


문제를 재귀적이게 생각할 수 있다. 어떤 노드에서 제일 먼 노드는 트리의 터미널 노드가 된다. 각 노드에서 제일 먼 노드들을 추려서 터미널 노드들을 구한다. 터미널 노드에서 가장 가까운 노드는 터미널 노드와 간선이 연결되어 있음이 자명하다. 이들을 간선으로 연결해준 뒤, 트리에서 구한 터미널 노드들을 제거한다. 이를 반복한다.


코드 보기


M. Variable Shadowing


문제에서 구현하라고 한 부분을 잘 코딩하면 되는 문제다. 언뜻보면 코딩이 복잡할 수 있지만 스택을 이용하면 비교적 쉽게 문제를 해결할 수 있다.


코드 보기


댓글
댓글쓰기 폼