티스토리 뷰

문제 링크


A. Cluster Analysis


$N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다.

$N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다.


코드 보기


B. Body Building


$N$개의 정점과 $M$개의 간선으로 이루어진 무방향성 그래프가 주어진다. 이 그래프에서 하나의 연결 요소를 덤벨로 구분할 수 있다. 덤벨이란, 하나의 손잡이 간선과 간선 양 쪽에 같은 수의 정점으로 구성된 완전 그래프가 있어야한다. 덤벨로 구분할 수 있는 연결 요소의 개수를 구하는 문제다.

편의상 입력으로 주어지는 그래프를 연결 그래프라고 하자. 우선 정점의 수 $N$은 짝수여야한다. $N = 2K$라고 할 때, $N-2$개의 정점의 차수는 $K-1$이어야 하고, 두 정점의 차수는 $K$이어야한다. 이를 통하여 손잡이 간선에 포함된 두 정점을 구할 수 있다. 이를 통해 그래프가 덤벨 모양인지 쉽게 확인할 수 있다.


코드 보기


C. Electric Bike


$N$개의 구간으로 이루어진 자전거 코스가 있다. 전기 자전거를 통해 이 구간 차례대로 모두 지나야한다. 전기 자전거의 동력에 따라 쓰이는 연료량과 얻는 힘이 다르다. $E$ 만큼의 연료가 있고 자전거 동력을 $K$번 바꿀 수 있을 때, $N$개의 구간을 지나기 위한 최소 추가 힘을 구하는 문제다.

D[i][j][k][l] = i번 구간까지 지났고 마지막 동력이 j이고 동력을 k번 바꿨고 사용한 총 연료량이 l일 때, 최소 추가 힘

위와 같이 DP 배열을 잡고 해결하면 된다. 시간복잡도는 $O(NKE)$이다.


코드 보기


D. Kevin's Problem


1부터 $N$까지의 수 $N$개로 이루어진 순열들이 있다. 하나의 순열이 있을 때, 특정 규칙을 통해 수 하나를 선택한다. 이 때 수 $P$가 선택되는 순열의 개수를 구하는 문제다.

D[i][j] = 수열의 마지막 수가 i고, 길이가 j인 증가 수열의 개수 (단, 수열에 $P$는 들어가지 않는다)

위와 같이 DP 배열을 정의하여 문제를 해결할 수 있다.

기본적인 아이디어는 수 $P$가 들어갈 위치를 정하고, $P$ 바로 앞에 오는 수를 정했을 때 경우의 수를 계산하면 된다.

아래와 같이 예외로 생각해주어야하는 경우가 존재한다.

  1. $P = N$ 인 경우
  2. $K = N-1$ 인 경우
  3. $P$가 순열의 마지막에 있는 경우

시간복잡도는 $O(N^2)$이다.


코드 보기


E. Cutting Tree


포레스트(1개 이상의 트리들로 이루어진 그래프)가 주어진다. 그리고 특정 간선을 지우는 질의와 두 정점이 연결되어 있는지 묻는 질의가 주어진다. 질의를 입력으로 주어진 순서대로 처리하는 문제다.

질의가 주어진 역순으로 문제를 뒤집으면, 질의는 간선을 지우는 것이 아니라 간선이 추가되는 질의로 바뀌게 된다. 이제 union-find를 통해 두 정점이 연결되어 있는지 확인할 수 있다.


코드 보기


F. Double Swords


$N$ 마리의 용이 있다. 용을 잡으려면 양손에 검을 하나씩 총 두 개의 검이 필요하다. 용 별로 필요한 검 하나는 크기가 정해지고, 나머지 검 하나는 특정 범위를 만족하면 된다. 이 때 모든 용을 잡기 위해 필요한 검의 최소 개수를 구하는 문제다.

편의상 왼손에 쥘 검을 크기가 정해진 검, 오른손에 쥘 검이 범위로 주어진 검이라 하자. 왼손으로 쥘 검의 크기들의 검은 반드시 필요한 검의 크기들이다. 이제 문제는 최소 개수의 검으로 오른손에 쥘 검들을 만들면 된다. 이는 여러 개의 구간들이 있고 모든 구간을 찍기 위해 필요한 점의 최소 개수와 같다. 이는 욕심쟁이기법으로 쉽게 구할 수 있다.


코드 보기


G. Prime Switch


$N$개의 전구가 있고, $K$개의 스위치가 있다. 전구는 1번부터 $N$번까지 번호가 매겨져 있다. 스위치에도 번호가 적혀있다. 이 번호들은 서로 다르며 소수(prime number)이다. 이 스위치를 누르면 스위치 번호의 배수가 적힌 전구들의 상태가 뒤집힌다. 이 때, 스위치를 적절히 눌러 켜져있는 전구의 개수를 최대화 하는 문제다.

$\sqrt{N}$보다 같거나 작은 번호를 가진 스위치는 많아야 11개다. 이 들에 대해 $2^{11}$가지의 경우에 대해 모두 처리하고 각 경우마다 $\sqrt{N}$보다 번호가 큰 스위치들에 대해서는 서로 독립이므로 욕심쟁이기법을 통해 전구의 개수를 최대화 할 수 있다.


코드 보기


H. I Want That Cake


A팀과 B팀에 각각 $N$명씩 사람이 있다. $M$개의 팬케잌이 있고, 한 사람이 한 개에서 $K$개의 팬케잌을 먹을 수 있다. 마지막 펜케잌을 먹는 사람이 속한 팀이 이기는 게임을 한다. 다만 두 팀이 번갈아가면서 진행하지 않고 미리 순서를 정해둔다. 두 팀에 속한 각 선수들이 최선을 다할 때 어느 팀이 이기는지 구하는 문제다.

D[i][j] = i번째 사람의 차례고, 남은 팬케잌의 개수가 j일 때 i번째 사람이 이기면 1, 지면 0

위와 같이 DP 배열을 정의한다.

i번째 사람과 i+1번째 사람이 같은 팀에 속한 경우와 그렇지 않은 경우에 따라 점화식이 달라지게 된다.

쉽게 생각하면 $O(NMK)$의 시간복잡도를 보이는데, 점화식의 특성을 잘 이용하면 $O(NM)$에 해결할 수 있다.


코드 보기


I. Maze Mayhem


$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 이제 $K$개 이하의 장애물을 설치해서 시작점에서 도착점으로 가지 못하게 해야 한다. 가능한 경우의 수를 구하는 문제다.

D[i][j][k][l] = i번 이동했고, 도달가능한 상황이 j이고, 설치한 장애물의 개수가 k이고, l번까지 장애물을 설치했을 때 경우의 수

위와 같이 DP 배열을 정의한다.

도달 가능한 상황이라 함은 i번 이동했을 때 도달 가능한 위치가 최대 $N$가지이다. 그러므로 가능한 상황의 수는 $2^N$가지이므로 길이가 $N$인 이진수로 나타낼 수 있다.

장애물을 l번 줄까지 놓았다는 것은 가능한 $N$개의 상황 중 l번까지 장애물을 설치했음을 의미한다. 중복으로 경우를 세는 경우에 대비하기 위해 필요하다.


코드 보기


J. Leveling Ground


길이가 $N$인 산 모양이 주어진다. 길이가 $M$인 구간을 공사해야한다. 공사는 구간에 속한 가장 낮은 높이에 맞춰 구간안에 있는 모든 땅을 판다. 이 때 비용은 파는 땅의 단면의 면적과 같다. 문제에 있는 그림에서 점('.') 하나는 비용이 1이며, 경사 ('/')는 비용이 0.5다. 이 때 공사 가능한 여러 구간들 중 최소 비용으로 공사할 수 있는 구간의 비용을 구하는 문제다.

길이가 $M$인 각 구간에 대해서 구간 내의 높이(점의 개수)의 합과 경사의 개수, 그리고 최소 높이를 알면 그 구간에 대한 공사 비용을 구할 수 있다. 이는 deque(Double-Ended Queue)와 같은 자료구조를 통해 구현할 수 있다.


코드 보기


K. Punching Robot


$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 미로 위에 $K$개의 장애물이 있는데 장애물들은 $1 \times 1$ 크기가 아닌 $3 \times 3$ 크기다. 장애물을 지나지 않고 시작점에서 도착점으로 가는 경로의 개수를 구하는 문제다.

$3 \times 3$ 크기의 장애물 하나를 $1 \times 1$ 크기의 장애물 9개로 바꾸고 문제를 생각한다. 그러면 총 90개의 장애물이 있을 수 있다. 이제 DP 배열을 아래와 같이 정의한다.

D[i] = 시작점에서 출발하여 장애물 i까지 장애물을 하나도 거치지 않고 가는 경우의 수

자세한 점화식은 생략한다.

문제에서 제일 중요한 것은 ${n}\choose{k}$를 $\mod 997$안에서 빠르게 구해야한다. 이는 뤼카의 정리를 이용하여 $\log {n+k}$ 시간안에 구할 수 있다. 일반적으로 생각할 수 있는 방법으로 구하면 $997!$이 997의 배수가 되어버려서 Modulo Inverse를 제대로 구할 수 없다.


코드 보기




댓글
댓글쓰기 폼