본문 바로가기

알고리즘

비행정 탑승

Best 20 · 13번Lv. 3완전 탐색

비행정 탑승

몸무게 측정 중인 라이캣

문제 설명

라이캣은 출정 명령을 내립니다. 각 지역에서 세력을 모았던 라이캣의 동료들은 각 지역에서 비행정을 타고 라이언 타운으로 향합니다. 이 비행정은 최소 무게 제한 K가 존재합니다.

비행정 한 대는 탄 동료들의 몸무게 합이 K 이상이어야 뜰 수 있습니다. 몸무게가 K 이상인 동료는 혼자 비행정 한 대를 띄울 수 있고, K 미만인 동료들은 몇 명이든 함께 타서 몸무게 합이 K 이상이 되면 비행정 한 대를 띄울 수 있습니다. 어느 비행정도 띄우지 못하고 남은 동료는 이미 뜨는 다른 비행정에 함께 타며, 이때 비행정 수는 늘지 않습니다.

라이캣은 동료들이 보다 넉넉한 공간에서 쉼을 취하며 올라오기를 원했어요. 동료의 몸무게를 담은 배열이 주어질 때, 모든 사람이 비행정에 탑승하기 위해 필요한 최대 비행정 개수를 구하세요.


제한 사항

  • 입력은 [몸무게 리스트, K] 형태입니다.
  • 친구들의 몸무게는 1 이상 100 이하의 정수입니다.
  • K는 0 이상 50 이하의 정수입니다.
  • 모든 동료의 몸무게를 합해도 K 미만이라 비행정을 한 대도 띄울 수 없으면 -1을 반환합니다.
  • 1 ≤ 동료 수 ≤ 10

입출력 예

몸무게K출력
[46, 26, 37, 32, 10]304
[22, 45, 1, 7, 5]152
[7, 36, 25, 12, 22]472

입출력 설명

[[46, 26, 37, 32, 10], 30]의 배열이 주어졌을 때 K는 30이기에 46, 37, 32는 혼자 탈 수 있습니다. 남은 10과 26을 더하면 30 이상이 되므로 둘이 함께 비행정 한 대를 띄울 수 있습니다. 만약 두 사람을 더해도 30에 못 미친다면, 두 사람은 이미 뜨는 다른 비행정에 함께 탑니다.

예시 테스트

#입력기대값
1[[46, 26, 37, 32, 10], 30]4
2[[22, 45, 1, 7, 5], 15]2
3[[7, 36, 25, 12, 22], 47]2

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.