https://www.acmicpc.net/problem/25586
문제요약
- 제한조건을 만족시키면서 주어진 트리의 순서를 지키며 트리를 재구성 할 수 있는지
- 자식 노드 개수의 제한 M
- 재구성했을 때 상-하 관계가 유지만 되면 됨
접근법
- 사실 25596 문제에서 떠올렸던 아이디어임
- 25596에서는 문제 조건에서 상-하 관계가 변경되는 경우가 새로운 박스가 추가될때만 임(합집합 어쩌고 하는 조건)
- 25586에서는 그런 조건은 없음 => 기존에 있던 박스에 넣어도 상-하 관계가 유지만 되면 됨(포함관계 조건)
- M의 최저 조건이 1이기 때문에 각각의 박스는 최소 한개의 공간여유가 있음
- 일렬로 쭉 늘어놓아도 상-하 관계가 유지만 된다면 가능하다는 이야기
- 즉 항상 추가 박스 없이도 가능하다는 이야기
- 재귀를 사용해서, 해당 노드가 개수 제한 M에 걸리면, 끝에 있는 노드를 떼다가 자식중 아무곳 빈자리에 넣어줌 => 이를 모든 노드, 모든 제한에 대해반복
- 어짜피 반복 해봤자 N^2 시간이 걸릴 것이고, 항상 가능함
newbieski