📍 문제
문제
레이몬드는 지구상에서 가장 큰 우표 수집가이며,
우표 수집가 파티에서 다른 모든 사람을 놀려대곤 합니다.
그래서 모두가 레이몬드를 좋아하지 않아요.
그러나 우표 수집가인 루시는 모두에게 사랑받고 있습니다.
그리고 그녀는 아래와 같은 한 가지 계획을 가지고 있습니다.
루시는 비밀리에 친구들에게 우표를 빌려 레이몬드보다 더 큰 컬렉션을 보여주어 파티에서 그를 창피하게 만들고자 합니다!
레이몬드는 자신이 제일 많이 우표를 많이 가지고 있다는 것을 확신하기 때문에 항상 얼마나 많은 우표를 보여줄 것인지 다 알려줍니다. 그리고 루시 역시 자신이 어느정도의 우표를 가지고 있는지 알기 때문에 얼마나 더 필요한지도 압니다.
그녀는 또한 친구들 중 몇 명이 우표를 빌려줄 수 있는지와 각각이 얼마나 빌려줄 수 있는지도 알고 있습니다.
그러나 그녀는 가능한 적은 수의 친구로부터 빌리고 싶으며, 너무 많이 필요하면 아예 빌리지 않기를 원합니다.
루시에게 몇 명의 친구로부터 우표를 빌려야 하는지 최소한의 숫자를 알려줄 수 있을까요?
입력
첫 번째 줄에는 시나리오의 수(= 테스트 케이스 수)가 주어집니다.
각 시나리오는 한 명의 수집가 파티를 설명하며,
첫 번째 줄에는 루시가 빌려야 하는 우표 수 (1에서 1000000까지)와 빌릴 수 있는 친구 수 (1에서 1000까지)가 나열됩니다.
두 번째 줄에는 그녀의 친구들이 제공하는 우표 수 (1에서 10000까지)가 나열됩니다.
출력
각 시나리오에 대한 출력은 "Scenario #i:"라는 줄로 시작하며, 여기서 i는 1부터 시작하는 시나리오 번호입니다.
그런 다음 루시가 친구로부터 우표를 빌려야 하는 최소한의 친구 수를 나타내는 한 줄을 출력합니다.
그렇게 해도 불가능한 경우 "impossible"을 작성합니다.
시나리오의 출력은 빈 줄로 끝납니다.
📍 아이디어
단순 sorting 문제.
우표를 내림차 순으로 정렬한 다음, 계산해주면 된다.
처음에는 필요한 수 만큼 합산하는 방식으로 했는데, 계속 오류가 나서 필요한 수에서 정렬한 리스트의 요소를 큰 것부터 차례대로 빼주는 식으로 계산하여 문제를 풀었다.
📍제출 코드
import sys
def main():
t = int(sys.stdin.readline().rstrip())
for i in range(1, t + 1):
print(f"Scenario #{i}:")
need, f = map(int, sys.stdin.readline().rstrip().split())
num = list(map(int, sys.stdin.readline().rstrip().split()))
num.sort(reverse=True)
a = 0
while need > 0 and a < f:
need -= num[a]
a += 1
if need <= 0:
print(a)
else:
print("impossible")
print()
if __name__ == "__main__":
main()
