티스토리 뷰

문제 링크


L. Wheel of Numbers


숫자 N개가 적힌 원판이 있다. 원판에 다트를 던져 한 곳을 맞춘다. 그 다트를 기준으로 시계방향으로 숫자 M개를 읽어 수 Z를 만든다. X ≤ Z ≤ Y 라면 점수를 획득한다. 원판과 X, Y가 주어졌을 때, 점수를 획득하는 경우의 수를 구하는 문제다.

아주 간단한 구현 문제다. M ≤ 9이므로, 64bit 정수형을 사용해서 X, Y, Z를 표현할 수 있다.



J. 3-Primes Problem


7이상 1000이하인 자연수 K가 주어졌을 때, 세 개의 소수의 합으로 나타내는 문제다. 세 개의 소수가 서로 다를 필요가 없다.

여러 방법으로 1000이하인 소수를 모두 구한다. 1000이하인 소수의 개수는 168개로 $168^{3}$가지의 소수 합을 모두 고려해도 시간안에 해결가능하다. 다만 테스트케이스 개수를 알 수 없으니, 전처리로 계산해두는 것이 좋다.



E. Log Jumping


$N$ 개의 통나무를 원형으로 배열해서 양 옆으로 인접한 통나무의 높이 차이 최대값을 최소화하는 문제다.

우선 통나무를 높이순으로 정렬한다. 제일 높이가 낮은 통나무 A를 가장 왼쪽에 두고, 제일 높이가 높은 통나무 B를 가장 오른쪽에 둔다. 나머지 통나무들은 높이 순서대로 위 아래 번갈아가면서 A와 B 사이에 둔다. 이렇게 원형으로 배열하면 높이 차이 최대값이 최소화 됨을 알 수 있다.



I. Stock


날 별로 주가가 주어지고, 날 마다 주식을 하나 사거나, 임의의 개수의 주식을 팔거나, 아무것도 안할 수 있다. 이 때 모든 날이 지나고 최대 이윤을 구하는 문제다.

어떤 날에 주식을 판다고 하면, 그 날보다 주가가 싼 주식은 모두 사는 것이 좋음은 자명하다. 그렇다면 오늘보다 이전이면서 주식이 비싼 날에는 오늘 팔 주식을 그 날 파는게 좋음 또한 자명하다. 그렇다면 DP 비슷하게 해결가능한데, 스택을 이용해서 오늘보다 주식이 비싸면서 가장 최근인 날을 구하고, 그 날 사이에 있는 주식을 모두 구매한 뒤 오늘 팔면 된다.



A. Coin Swap


그래프의 정점 위에 검정색 혹은 하얀색 동전이 놓여있고, 간선으로 인해 인접한 두 정점에 있는 동전을 서로 바꿀 수 있다. 원하는 최종 상태가 주어졌을 때, 최소 회수로 동전을 바꿔 최종 상태를 만드는 문제다.

편의상 하얀색 동전을 동전이 없는 것으로 볼 수 있다. 좀만 생각해보면 아주 재미있는 사실을 알게되는데, 검은색 동전이 서로 독립적이게 움직이는 것으로 볼 수 있다는 것이다. 그러면 이 문제는 초기에 검은색 동전이 있는 위치와 최종 상태에서 검은색 동전이 있는 위치들 사이의 거리를 가중치로 두고 가중치 있는 이분매칭이 된다. 가중치 있는 이분매칭은 MCMF(Min Cost Max Flow)나 헝가리안 메소드로 해결가능하다.



C. Grid


$N \times M$ 크기의 직사각형 격자위에 수가 적혀있다. 가로 혹은 세로로 인접한 두 칸을 선택해서 1을 감소시키는 연산 혹은 임의의 한 칸에 있는 수를 1 감소시키는 연산이 있다. 이 때, 모든 칸을 0으로 만드는 연산의 최소 회수를 구하는 문제다.

우선 첫 번째로 해야하는 것은 인접한 두 칸으로 최대한 많이 감소 시키는 것이다. 격자에 적힌 수들의 합을 S 라 하고, 두 칸으로 감소하는 연산을 한 회수를 F 라고 할 때, 총 회수는 S - F 가 된다. 따라서 F의 가능한 최대값을 구하면 이 문제를 해결할 수 있다. 이는 Maximum Flow 로 해결가능하다. 직사각형 격자판을 체스판 처럼 검정색과 흰색으로 칠한다고 했을 때, 인접한 두칸의 색은 다르다. 이 색으로 이분 매칭 꼴로 그래프를 만들어 Source에서 검정색 칸으로 가는 유량은 칸에 적힌 수, 흰색 칸에서 Sink로가는 유량은 칸에 적힌 수로 하고, 인접한 두 칸을 연결하는 유량은 $\infty$로 하고 최대 유량을 구하면 F가 된다.



G. Path


히스토그램이 주어졌을 때, 히스토그램 왼쪽 아래 점($v_0$)에서 히스토그램 변 위의 점까지 가는 최단 거리의 합을 구하는 문제다.

문제에서 입력으로 $v_0$부터 시작해서 반시계 방향으로 주어지는데, 이를 $v_0$부터 시작하는 시계방향 순서로 바꿔야한다. 이 때, 쿼리로 들어오는 변 위의 점도 포함시킨다. $v_0$에서 어떤 점으로 가는 최단 경로는 항상 아래로 볼록한 모양을 띈다. 이를 이용해서 시계방향 순서로 구한 점을 차례대로 convex hull을 구해주면 된다.



K. Tree Edit


자식들의 순서가 중요한 트리 두 개가 주어진다. 라벨을 바꾸거나, 단말 정점을 지우거나, 어떤 정점을 임의의 위치에 추가하는 연산이 있다. 트리 하나를 다른 트리로 만드는 최소 연산 회수를 구하는 문제다.

$O(N^4)$이 될 것 같은 동적계획법 풀이가 있다. 아직 나는 증명은 못했지만, 팀원 배근우의 말로는 이게 결국 $O(N^2)$이 된다고 한다. 시간이 날 때 생각해보고 관련해서 수정하겠다.

방법은 정점 a의 서브트리를 정점 b의 서브트리로 바꾸는 최소 연산 회수를 구하는 문제를 풀면 된다. 이는 재귀적으로 해결 가능하며, LCS를 구하는 과정과 매우 흡사하다. 자세한 설명은 생략하겠다.

정점 a의 서브트리 크기를 $n$, 정점 b의 서브트리 크기를 $m$이라고 하자.

시간복잡도는 $T(n, m) = knm + \sum\limits_{i}\sum\limits_{j} T(n_i, m_j)$가 된다. (여기서, $\sum\limits_{i} n_i = n-1, \sum\limits_{j} m_j = m-1$).



H. Polynomial


문제에서 함수 $S(n)$을 정의하고, $S(n)$을 $n$으로 된 다항식으로 나타냈을 때, 기약분수의 분자 절대값의 합을 구하는 문제다.

새로운 함수 $z$를 정의하자. 그러면 함수 $S(n)$는 아래와 같이 정리할 수 있다.



함수 $z$는 Faulhaber Formula에 의해 아래처럼 정리된다.



이를 이용해서 $S(n)$에서 $n^i$항에 대한 계수를 구할 수 있다. 문제에서 준 힌트에 의해 $(n+1)^{k+1}$은 아래와 같이 다시 쓸 수 있다.




F. Odd Cycle


단순 방향성 그래프가 주어졌을 때, 정점 중복이 없는 홀수 길이 싸이클 아무거나 하나 찾는 문제다.

홀수 싸이클이 있다면 SCC 안에서만 있을 수 있다. 그러면 하나의 SCC에 대해서 홀수 싸이클이 있는지 찾는 방법을 설명하겠다.

한 정점을 잡고 DFS Tree를 만든다. 깊이에 따라 검정색과 흰색을 번갈아가면서 색칠한다. 색이 같은 정점 p, q가 있고, p에서 q로 가는 간선이 있으면 홀수 싸이클이 있는 것이고, 아닌 경우 없다. DFS Tree에서 p와 q의 LCA를 정점 t라고 하자. 그래프가 SCC 이므로 q에서 t로 가는 경로는 항상 존재한다. q => t로 가는 임의의 경로를 찾고 그 경로의 길이를 $l_{qt}$이라고 하자. DFS Tree 안에서 t => q로 가는 경로의 길이를 $l_{tq}$라 하자. 만약 $l_{qt} + l_{tq}$가 홀수라면 우리는 홀수 싸이클을 찾은 것이다.

$l_{qt} + l_{tq}$가 짝수일 때 홀수 싸이클을 구하면 된다. DFS Tree 안에서 t => p로 가는 경로의 길이를 $l_{tp}$라고 하자. p와 q의 색이 같으므로 $l_{tp}$와 $l_{tq}$의 parity가 같다. 그러면 q => t => p ->q는 홀수 싸이클이 된다. 그러므로 항상 홀수 싸이클을 구할 수 있다.

이제 해결해야되는 것은 "정점 중복이 없는" 홀수 싸이클을 구하는 것이다. "정점 중복이 있는" 홀수 싸이클에서 "정점 중복이 없는" 홀수 싸이클은 항상 도출 가능하며 방법이 어렵지 않다.

정점 색 중복을 일으키는 간선이 없을 때는 항상 홀수 싸이클이 없다는 것을 증명하는 것이 남았다. 이 증명도 어렵지 않다.

이 문제를 해결하는 시간복잡도는 $O(V + E)$ 다.



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함