Sunday, July 6, 2014

NWERC 2006 'The Bookcase'

Problem Link

위상을 정렬해주기 위해 h순으로 정렬을 하면

.... h(a)  .... h(b) .... h(n) 이렇게 3부분으로 책장이 구성된다.

1~a까지는 모든 책장, a+1부터 b까지는 뒤에 두 개의 책장, b+1부터 n까지는 마지막 책장의 두께에 영향을 끼칠 수 있다.

h를 결정해서 하려면 최댓값을 최소화하는 부분문제를 풀어야하는데 결정 알고리즘을 써도 안되고, dp를 하자니 잘 안 떠올라서 두께 t를 결정해보기로 했다.

그러면 어떤 2개의 책장의 두께 ta와 tb를 결정하면 나머지 책장의 두께는 sum(t)-ta-tb가 된다. 그리고 ta와 tb일 때, d[ta][tb]를 책장 2개의 높이의 최솟값이라 하면, d[i][j] = min(d[ta-t[i]][tb]+h[i], d[ta][tb-t[i]]+h[i]) 같은 꼴로 구할 수 있다. 답은 min( max(ta, tb, sum(t)-ta-tb)*(max_h + d[ta][tb])가 된다.

시간복잡도는 O(N * sum(t)^2)이 된다.

h 중 최댓값은 반드시 한 책장의 높이를 차지한다는 것을 깨달으면, 2개의 책장만 결정해도 되는 게 중요하다고 생각된다.

Source Code

No comments:

Post a Comment