티스토리 뷰

문제 링크


A. Awkward Group


$N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다.

초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그래프인지 확인한다. 만약 완전 그래프라면 그 연결 요소에 있는 정점들이 문제의 조건을 만족하는 집합 $F$가 됨이 자명하다. 완전 그래프인지 확인하는 것은 연결 요소 내의 정점 개수와 간선 개수를 비교하여 O(1)에 해결 가능하다. 만약 가중치가 같은 간선이 여러 개라면 한 번에 추가해야한다.


코드 보기


B. Card Game


점수가 적힌 $N$개의 카드가 일렬로 놓여있다. 한 턴에 가장 왼쪽 카드나 가장 오른쪽 카드를 가져갈 수 있다. 두 사람이 번갈아가면서 더 이상 가져갈 카드가 남아있지 않을 때까지 최선의 전략으로 게임에 임한다. 최종 점수는 자신이 가져간 카드에 적힌 점수의 합이다. 첫 턴을 진행한 사람이 얻는 점수를 구하는 문제다.

D[i][j] = i번째 카드부터 j번째 카드만 있다고 했을 때, 첫 턴을 시작하는 사람이 가져가는 점수 합의 최대값

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 카드부터 j번째 카드까지 적힌 점수 합) - min(D[i+1][j], D[i][j-1])


코드 보기


C. Consecutive Ordering


(문제 설명 생략)

각 구간에 대해서 자신과 교차하는 구간 번호 범위를 O(N)에 계산할 수 있다. i번 구간에 대해 교차하는 구간 번호 범위를 S[i] ~ E[i]라고 하자. 입력으로 주어진 새로운 순서에서 S[i] ~ E[i]가 연속하게 나오는지 모든 i에 대해 확인을 해주어야한다. 어떤 수 k(1 ≤ k ≤ N)가 입력으로 주어진 새로운 순서에서 몇 번째 순서인지 R[k]에 저장해두자. S[i] ~ E[i]가 새로운 순서에서 연속하게 나오는지 확인해주는 것은 S[i] ≤ j ≤ E[i]인 j에 대해 R[j]의 최대값과 최소값의 차이가 E[i] - S[i]인지 비교해주면 된다. 이는 Binary Indexed Tree나 Segment Tree, Interval Tree 등을 이용해서 시간복잡도 $O(N \lg N)$에 해결 가능하다.


코드 보기


D. Diameter


정점의 개수가 N개인 트리가 주어진다. 트리 간선의 가중치를 0까지 줄일 수 있고 가중치 1을 줄이는데 비용이 1만큼 든다. 이 때, 트리의 지름을 D이하로 만드는 최소 비용을 구하는 문제다.

차수가 2이상인 정점을 루트로한 Rooted Tree를 구성한다. 모든 정점에 대해 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D를 넘지 않으면 전체 트리의 지름 또한 D 보다 크지 않다. 이는 필요충분조건이다.

그러면 처음에 구성한 Rooted Tree에서 깊이가 낮은 순서대로 정점들을 처리하는데, 정점들을 처리할 때 그 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D이하가 되도록하는 최소 비용을 계산해주면 된다.


코드 보기


E. Grid Aliens


격자에서 점의 부분 집합 W를 잡고, Q = U - P라 했을 때, 문제에서 나타내는 식의 최대값을 구하는 문제다.

이 문제는 네트워크 플로로 해결할 수 있다. Google CodeJam 2015 Round 2의 C번 문제와 유사한 min-cut으로 해결한다.

max(CostW + CostQ - CostWQ)를 다시 쓰면 N- min(CostW` + CostQ` + CostW`Q`)로 쓸 수 있다. 여기서 W` = Q이고, Q` = W 이다.

아래와 같이 그래프를 구성하고 min-cut을 구하면 min(CostW` + CostQ` + CostW`Q`)을 구할 수 있다. 까닭은 코드잼의 C번 문제와 비슷하다. 



이와 비슷한 문제로는 2014년 전대프연 Bus Assignment 문제가 있다.


코드 보기


F. Merging Files


수열이 주어졌을 때, 인접한 두 수를 합칠 수 있다. 합치는 비용은 두 수의 합이고, 전체를 하나의 수로 합하는데 최소 비용을 구하는 문제다.

D[i][j] = i번째 수부터 j번째 수만 있다고 했을 때 하나의 수로 합치는 최소 비용

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 수부터 j번째 수의 합) + min(D[i][k] + D[k+1][j]) for i ≤ k < j

시간복잡도는 $O(N^3)$이다. Knuth Optimization을 통해 $O(N^2)$에도 해결가능하다.


코드 보기


G. Monotone Walkway


(0, 0)에서 시작하여 왼쪽으로 이동하지 않으며 방향을 90도씩만 꺽으며 이동하는 로봇이 방문한 점들이 주어진다. 불가능한 입력은 주어지지 않으며, 입력으로 주어진 점들의 순서를 찾아내는 문제다. 로봇이 방향을 꺽은 점은 항상 입력으로 주어진다.

x = a 꼴의 직선위에 있는 점들을 생각해보면 로봇이 이 직선을 위에서 아래로 이동했는지, 아래에서 위로 이동했는지 판단할 수 있다. 이를 판단하여 순서를 매겨주면 되는 쉬운 문제다.


코드 보기


H. Palindromic Numbers


입력으로 주어진 자연수 N에 대해 N을 B진법(2 ≤ B ≤ 64)로 나타냈을 때 회문이 되는지 판단하는 문제다.

2이상 64이하의 B에 대해 B진법으로 표현해보고 회문이 되는지 확인해주면 된다.


코드 보기


J. Pythagorean Expectation


야구에서 팀에 피타고라스 기대값을 정의할 수 있다. 시즌 시작부터 시즌 끝까지 야구 경기 기록이 주어지고, 시즌 내에서 팀들의 피타고라스 기대값을 계산하고, 최대값과 최소값을 구하는 문제다.

문제에서 하라는대로 하면 되는 간단한 문제다.


코드 보기


저작자 표시
신고
댓글
댓글쓰기 폼