예상 난이도: 3번
DP 테이블을 다음과 같이 정의합니다. D[i] = (i를 제곱수들의 합으로 표현할 때 항의 최소 개수)
i를 제곱수들의 합으로 나타내었을 때 어떤 제곱수 jj 가 등장한다고 가정합니다. 그러면 항의 개수는 i - j*j
의 항들에 jj 항 한 개를 추가했으므로 D[i - j*j] + 1
이 됩니다. i보다 작은 모든 제곱수 j*j 를 돌아보며 D[i - j*j] + 1
중 최솟값을 찾으면 D[i] 의 값을 알 수 있습니다.
각각의 i에 대해 i보다 작은 제곱수를 돌아보는 시간이 sqrt(i)만큼 걸리므로, 총 시간복잡도는 O(N sqrt(N))입니다. 이는 시간 제한 안에 통과하기에 충분히 빠릅니다.
예상 난이도: 1번
로프 k개를 사용한다고 가정하면, N개의 로프 중 한계 중량이 가장 큰 k개의 로프를 고르는 것이 최적의 방법입니다. 이때 들 수 있는 최대 중량은 "k개의 로프 중 한계 중량이 가장 작은 로프"의 한계 중량에 k를 곱한 값이 됩니다. (무게가 1/k로 분산되므로)
따라서 로프를 한계 중량의 내림차순으로 정렬한 뒤 (k번째 로프의 한계 중량) × k 중 최댓값을 구하면 됩니다.
예상 난이도: 5번
가장 큰 팬케익부터 아래에 두겠습니다. 먼저 가장 큰 팬케익의 위치를 찾아서 그 위치까지 뒤집으면 가장 큰 팬케익이 맨 위에 올라오게 됩니다. 이제 전체를 뒤집으면 가장 큰 팬케익이 맨 아래로 갑니다. 점점 더 작은 크기의 팬케익에 비슷한 작업을 반복하면 각 팬케익당 2번의 뒤집기를 사용해서 정렬할 수 있습니다.
문제는, 뒤집기 횟수가 최대 2n이 아니라 2n-3번이라는 겁니다. 팬케익 두 개가 남았을 때 필요한 뒤집기 횟수가 2×2=4번이 아니라 1번임을 이용하면 3회의 뒤집기를 줄일 수 있습니다.
예상 난이도: 4번
상한액을 x라고 하면, x가 증가할수록 배정되는 총 예산이 증가합니다. 따라서 배정되는 총 예산이 M 이하가 되는 x를 이분 탐색으로 찾을 수 있습니다. 상한액 x가 지방별 예산의 최댓값보다 작으면 x를, 그 외의 경우 지방별 예산의 최댓값을 출력하면 됩니다.
예산을 정렬하고 상한액을 점점 증가시키면서 푸는 방법도 있습니다.