PS 이야기

문제 링크E. Association for Computing MachineryN개의 문제가 있는 ICPC 세트가 있다. 각 문제별로 푸는 시간이 주어진다. p번 문제의 First Solve 상을 노려야하기 때문에 p번 문제를 제일 먼저 풀고 제일 좋은 전략으로 문제를 해결할 때, 푼 문제 수와 패널티를 구하는 문제다. 문제는 한 번에 맞는다고 가정한다.p번 문제를 0번지에 놓고 1번지부터 이후를 푸는 시간순서로 정렬한 다음에 순서대로 시간이 300분..

문제 링크 A. Cluster Analysis $N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다. $N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다. #include <stdio.h> #inclu..

코드포스 GYM 링크 A. Avoiding the Apocalypse 내가 아직 풀지 않았다. B. Button Bashing $n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다. #include <stdio.h> #include <queue> using namespace std; int T, N, ..

온라인 아카이브 링크 A. The Mountain of Gold? 0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다. 일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 ..

온라인 아카이브 링크 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 &..

코드포스 GYM 링크 B. Colored Blanket 이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다. 담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$ 위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 ..