DP[i][j] 를 i일차를 살아내야 하는데 쿠폰이 j개인 상황에서의 최소 비용이라고 합시다.
하루에 아무리 쿠폰을 득달같이 모아도 2개씩 모을 수 있으므로 j <= 2i를 만족합니다. 따라서 DP table의 크기는 \(O(n^2)\)이 됩니다.
이 문제는 DP값을 이전에서 '불러오는' 것보다 뒤로 '뿌려주는'게 훨씬 편합니다.
즉 DP[i][j] = min(DP[i][j], DP[i-3][j-2]+37); 보다는 DP[i+3][j+2] = min(DP[i+3][j+2], DP[i][j]+37); 식으로 구현하는 게 좋습니다.
가능한 상태 전이를 모두 생각하는 것으로 풀이를 줄이겠습니다.
i일에 수영이가 여행을 가지 못하는 경우 :
(i,j) -> (i+1,j). 추가비용 0
i일에 수영이사 여행을 갈 수 있는 경우 :
(i,j) -> (i+1,j). 추가비용 10000
(i,j) -> (i+3,j+1) 추가비용 25000
(i,j) -> (i+5,j+2) 추가비용 37000
(i,j) -> (i+1,j-3) 추가비용 0 (j >= 3)
단, 답은 DP[n+1][0] ~ DP[n+5][2*(n+5)] 중 최솟값임에 주의합시다.
허프만 알고리즘의 간단한 응용입니다.
priority_queue를 이용해서 값이 가장 작은 두 카드 x, y를 뽑아서 합쳐준 후 x+y 2개를 다시 priority_queue에 넣는 작업을 반복하면 됩니다.
시간복잡도는 \(O(M\lg N)\)이 됩니다.
(틀린 증명이 있었던 자리)
모든 리프 노드에 대해 깊이를 합한 값이 홀수이면 승리, 짝수이면 패배입니다.
리프 노드에 대한 깊이는 DFS를 이용하여 구할 수 있습니다. 혹시 모르니 의사코드도 드리겠습니다.
int dfs(x, p, dep):
boolean isLeaf = True
int ret = 0
for u is adjacent to x:
if u == p: continue
isLeaf = False
ret += dfs(u, x, dep+1)
if isLeaf:
return dep
else:
return ret
세그먼트 트리를 활용하는 문제의 대표격입니다.
시간 관계상 jason9319님의 풀이로 대체합니다.
죄송합니다.
한 번 짤 테면 짜 봐! 라는 심정으로 넣은 계산 더러운 DP 문제였습니다.
이런 문제는 풀지 않는 것이 이롭습니다.
Diuven이 갓문제라고 추천했습니다. 제가 내자고 안 했습니다. 살려주세요.
문제에서 그래프가 연결그래프가 아니라는 조건이 있는데, 그냥 무시하고 하나의 연결 컴포넌트를 보면 연결그래프로 생각할 수 있습니다. 이제 몇 가지 관찰을 합시다.
에지를 없애거나 만드는 과정을 에지를 "toggle한다"고 합시다. 즉 on 상태의 에지를 끄거나, off 상태의 에지를 되살리는 작업을 말합니다. 이 과정에서 해당 에지의 양 끝점은 차수가 1 변화하겠죠.
홀수 차수의 점을 \(o\), 짝수 차수의 점을 \(e\)라고 하면, 그 둘을 잇는 에지를 toggling하여 다음을 만들 수 있습니다.
\((o,o) \leftrightarrow (e,e)\) : 두 개의 even-degree 정점을 쌍소멸시킬 수 있다.
\((o,e) \leftrightarrow (e,o)\) : 한 정점의 even-ness (...)를 다른 정점으로 이동시킬 수 있다.
다시 말해, 적절한 작업을 통해 even-degree 정점의 개수를 증가시키지 않고 even-ness를 마음대로 전이시킬 수 있습니다.
따라서 DFS tree를 구성하고 자식 노드가 even일 경우 부모 - 자식 간의 edge를 toggling하여 even을 소멸 / 전이시킬 수 있습니다. 즉 한 노드의 DFS가 끝날 때, 자신을 제외한 서브트리의 모든 노드가 odd임이 보장되게 할 수 있습니다.
이 과정에서 even degree 정점은 0개/2개씩 감소합니다.
따라서 DFS 작업 종료 이후에 루트가 even인 컴포넌트가 존재하는 경우 애초에 컴포넌트의 even-degree 정점 수가 홀수 개였다는 뜻이므로 불가능. -1을 출력하면 됩니다. 그렇지 않은 경우는 on 상태의 에지를 모두 출력하면 됩니다.