6148번 - Bookshelf 2
Farmer John이 소 도서관을 위해 새로운 책장을 샀는데, 공간이 부족하여 이제 유일한 공간은 책장 맨 위에 있습니다.
소는 총
N마리(1 ≤ 𝑁 ≤ 20)이며, 각각의 키 𝐻𝑖 (1 ≤ 𝐻𝑖 ≤ 1,000,000)를 가지고 있습니다. 책장의 높이는 B(1 ≤ B ≤ 𝑆, 여기서 S는 모든 소들의 키의 합)입니다.
소들이 책장 맨 위에 도달하기 위해서는, 하나 이상의 소가 서로 쌓여서 서야 합니다. 이들의 키 합이 책장 높이 이상이 되어야 책장 맨 위에 도달할 수 있습니다.
책장의 높이에 딱 맞추는 것이 이상적이며, 필요 이상의 높은 쌓기는 위험할 수 있으므로, 책장 높이에 도달할 수 있는 최소한의 소들을 선택하여 최소한의 초과 높이를 만들어야 합니다.
입력 예시
출력 예시
댓글을 작성하려면 로그인해야 합니다.
rhtjdxo 2년 전
Farmer John이 소 도서관을 위해 새로운 책장을 샀는데, 공간이 부족하여 이제 유일한 공간은 책장 맨 위에 있습니다.
소는 총
N마리(1 ≤ 𝑁 ≤ 20)이며, 각각의 키 𝐻𝑖 (1 ≤ 𝐻𝑖 ≤ 1,000,000)를 가지고 있습니다. 책장의 높이는 B(1 ≤ B ≤ 𝑆, 여기서 S는 모든 소들의 키의 합)입니다.
소들이 책장 맨 위에 도달하기 위해서는, 하나 이상의 소가 서로 쌓여서 서야 합니다. 이들의 키 합이 책장 높이 이상이 되어야 책장 맨 위에 도달할 수 있습니다.
책장의 높이에 딱 맞추는 것이 이상적이며, 필요 이상의 높은 쌓기는 위험할 수 있으므로, 책장 높이에 도달할 수 있는 최소한의 소들을 선택하여 최소한의 초과 높이를 만들어야 합니다.
입력 예시
출력 예시