RUN@KAIST 6/29 방학 연습 풀이

1. MP3 Songs

아무 생각 없이 아스키 순으로 정렬하면 나옴. 앞으로는 셋에 이런 문제를 넣지 않겠습니다.

2. Reconstruction Trees

올바른 입력임을 가정할 때 preorder와 inorder가 주어지면 유일하게 트리를 결정할 수 있다. preorder의 맨 앞에 있는 원소가 루트이고, inorder에서 이 루트를 찾으면, 왼쪽 서브트리와 오른쪽 서브트리를 찾을 수 있다. 우리는 여기서 루트와, 왼쪽 서브트리의 preorder / inorder, 오른쪽 서브트리의 preorder / inorder를 찾을 수 있기 때문에 재귀적으로 전체 트리 모형을 유추할 수 있다. 이 트리를 postorder traversal하면 된다. 여담으로 트리를 만든다는 식으로 서술했지만 실제로는 찾아가면서 재귀 호출 안에서 찍어줘도 된다.

올바른 트리가 아니면 Invalid tree를 찍어줘야 하는 줄 몰랐다. 그래도 AC 받을 수 있다 (...)

3. 500-yen Saving

살 수 있는 물건의 subset은 2^N개인데, subset이 고정되었을 때 문제를 푸는 방법부터 생각해 보자. 1000원짜리만을 냈을 때 받는 거스름돈을 rem_i (0 <= rem_i <= 999) 라고 정의하고, 1000원을 제외한 (100원 이하의) 동전들의 합을 c라고 했을 때, 우리가 할 수 있는 행동은 다음 3가지 중 하나다.

 * rem_i >= 500 이면, 어쨌든 500원이 들어온다. 동전의 합에서 rem_i - 500이 더해진다. 

 * rem_i < 500, rem_i + c >= 500인 경우를 생각해 보자. 가게에서 물건을 살 때 일정한 정도의 동전을 더 내서 500원 이상 1000원 미만의 거스름돈을 받아야 한다. 다행이도, c는 100원 이하의 동전만으로 이루어져 있기 때문에, rem_i에다가 동전을 하나 하나 더해 나가면 500원 이상 1000원 미만의 거스름돈을 받을 수 있다. 500원을 받을 수 있고, 동전의 합에서 rem_i - 500이 더해진다. 

 * rem_i < 500, rem_i + c < 500이면 동전을 다 주고도 500원을 받을 수 없다.

고로 rem_i + c >= 500 이냐 아니냐에 따라서 case가 결정된다. c의 상한은 500N 정도이니, 이를 통해서 DP를 세워보자.

 " DP[위치, c] : 현재 위치에서, 동전의 합이 c일 때, 최대 500원, 개수가 같을 때 최소 가격을 반환. "

현재 최대의 500원을 주지 않는 상태를 무시해도 괜찮을까? 그 상태가 나중에 최대의 500원을 주는 상태를 역전한다고 가정하면 모순이 된다. 고로 최대의 500원을 주는 상태만을 고려하는 이 DP로도 문제를 해결할 수 있다.

4. Floating Formation

먼저 문제에 적혀있는 대로 degree 1인 정점들을 지워나가자. 지워나가다 보면 결국 사이클에 막히게 될 것이고 (항상 사이클이 존재한다는 게 문제 조건에 적혀있음), 사이클에 막히기 전까지 지워나간 정점들은 포레스트를 이룬다. 이 포레스트를 슈퍼 노드 하나에 묶어주면 트리 하나를 만들 수 있다. 슈퍼노드를 0이라고 하면 예제 1은 0 - 4, 4 - 5, 5 - 6 으로 이루어진 트리라고 할 수 있겠음. 

이제 rooted tree가 주어졌을 때, 루트와 리프를 잇는 K개의 path를 사용해서 최대한의 정점을 덮는 문제가 된다. 이는 그리디 알고리즘으로 해결할 수 있다. 선택할 수 있는 리프 중 추가로 덮는 노드가 가장 많은 리프를 그때 그때 탐욕적으로 골라주면 O(N^2) 알고리즘이 된다. 이를 O(N)으로 최적화하기 위해서는, 현재 선택할 수 있는 노드 중에서 가장 깊은 노드를 이어주고, 나머지 정점들에 대해서는 따로 dfs를 통해서 개별적으로 처리하게 하는 방법을 사용하면 된다. 코드로 쓰는게 이해가 더 쉬울듯. https://gist.github.com/koosaga/f873af82061fb59fa34961b03b47bbbd