DP[i][j] 를 i일차를 살아내야 하는데 쿠폰이 j개인 상황에서의 최소 비용이라고 합시다.
하루에 아무리 쿠폰을 득달같이 모아도 2개씩 모을 수 있으므로 j <= 2i를 만족합니다. 따라서 DP table의 크기는 O(n2)이 됩니다.
이 문제는 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(MlgN)이 됩니다.
(틀린 증명이 있었던 자리)
모든 리프 노드에 대해 깊이를 합한 값이 홀수이면 승리, 짝수이면 패배입니다.
리프 노드에 대한 깊이는 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)↔(e,e) : 두 개의 even-degree 정점을 쌍소멸시킬 수 있다.
(o,e)↔(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 상태의 에지를 모두 출력하면 됩니다.