PS 이야기

온라인 아카이브 링크 A. Number Assignment 문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다. D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합 점화시은 아래와 같다. D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i) 총 시간복잡도는 $O(N^2M)$이다. #include #include using namespace std; int T, N, M; int A[101], D[101][101]; int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); s..

코드포스 GYM 링크 B. Colored Blanket 이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다. 담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$ 위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다. #inc..