PS 이야기

문제 링크 A. Cluster Analysis $N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다. $N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다. #include #include int T, N, K; int A[101], par[101]; int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); } int main() { int ts = 0, i, j; for ..

코드포스 GYM 링크 A. Avoiding the Apocalypse 내가 아직 풀지 않았다. B. Button Bashing $n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다. #include #include using namespace std; int T, N, K; int D[3601], A[17]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &K); for (i=1;i<=N;i++) scanf("%d", A+i); for (i=0;i<3601;i++) D[i] = 2..

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

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

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