問題
개미사냥꾼 정올이는 아주 커다란 개미굴을 발견했다.
개미굴은 하나의 입구 방을 기준으로 아래로 최대 2개의 방, 최소 0개의 방으로 이어져있다.
각 방의 크기는 모두 다를 수 있어서 그 안에 들어있는 개미의 수도 다를 수 있다.
정올이가 챙겨온 개미보관함은 그 크기가 충분하지 않아
개미굴의 각 방들을 K개의 그룹으로 묶어서 가둬두고 한번에 하나의 그룹씩 챙겨가려고한다.
그룹은 인접한 방들끼리만 묶을 수 있기에, 그룹을 K개로 나누는 방식은 K-1개의 통로를 차단하는 방식으로 진행한다.
이 때, 최대한 효율적으로 그룹을 나누기 위해 가장 개미의 수가 많은 그룹의 개미 수를 최소화 시켜야한다.
개미의 수가 가장 많은 그룹의 인원이 최소가 되도록 그룹을 분배하였을때
해당 최대 그룹의 개미의 수를 출력하는 프로그램을 작성하시오.
輸入
첫 번째 줄에 개미 방의 수 N (1 <= N <= 100,000)와 그룹의 수 K(1 <= K <= 30)가 입력된다.
두 번째 줄에 공백을 기준으로 i번 방의 개미 수가 N개 입력된다.
이 때, i(1 <= i <= N)번 방에 들어가는 개미의 수 A는 0 이상 1,000 이하이다.)
세 번째 줄부터 N줄에 걸쳐 i번 방의 왼쪽과 오른쪽 방의 번호가 입력된다. (-1은 방이 없는 경우이다)
輸出
개미의 수가 가장 많은 그룹의 인원이 최소가 되도록 그룹을 분배하였을때 해당 최대 그룹의 개미의 수를 출력하시오.
範例
10 3
15 10 5 10 30 20 20 20 30 40
5 8
-1 -1
4 7
1 -1
-1 -1
-1 -1
10 9
-1 -1
-1 6
-1 2
75
標籤
來源
JUNGOL - klee
需要登入才能撰寫程式碼。