파이썬 코딩테스트 강좌, 블루레이 만들기

문제 설명

회사에서 새로운 블루레이 디스크 제작 시스템을 개발하려고 합니다. 각 블루레이는 특정한 크기를 가지고 있으며, 이를 최적화하여 가장 많은 양의 데이터를 저장하는 블루레이를 만들어야 합니다. 주어진 블루레이의 용량과 각 파일의 용량을 바탕으로, 최대한 많은 파일을 블루레이에 담을 수 있도록 하는 프로그램을 작성하세요.

문제 정의: N개의 파일이 있고, 각 파일은 양의 정수 크기를 가지며, 블루레이의 용량이 주어졌을 때, 블루레이의 용량을 초과하지 않으면서 담을 수 있는 최대 파일 수를 구하는 프로그램을 작성하시오.

입력 형식:
첫 번째 줄에 블루레이의 용량 C (1 ≤ C ≤ 10000)과 파일의 개수 N (1 ≤ N ≤ 100) 가 주어진다.
두 번째 줄에 N개의 파일 크기가 주어진다 (1 ≤ 파일 크기 ≤ 1000).

출력 형식:
블루레이에 담을 수 있는 최대 파일 수를 출력하시오.

문제 분석

이 문제는 주어진 파일들의 크기가 블루레이의 용량 C를 초과하지 않도록 조합하여 최대 파일 수를 구하는 문제입니다. 블루레이에 담길 수 있는 파일의 수를 최대화하기 위해서는 사전에파일들을 적절히 정렬하고, 적절한 탐색 방식으로 문제를 해결해야 합니다.

문제를 해결하기 위한 기본 전략은 다음과 같습니다:

파일 크기를 오름차순으로 정렬한다.
정렬된 파일들을 순차적으로 더해가며, 블루레이의 용량 C를 초과하지 않을 때까지 파일을 추가한다.
용량을 초과하면 파일 추가를 중단하고, 현재까지 추가한 파일의 수를 반환한다.

문제 해결 과정

단계별로 문제를 해결하는 과정을 살펴보겠습니다.

1단계: 입력 받기

먼저, 블루레이의 용량과 파일의 수, 그리고 파일들의 크기를 입력받습니다. 입력은 표준 입력을 통해 이루어집니다. Python의 input() 함수를 사용하여 데이터를 받을 수 있습니다.

2단계: 데이터 정렬

입력받은 파일 크기를 오름차순으로 정렬합니다. 이는 파일을 추가할 때, 작은 파일부터 담아가기 위해 필요합니다. Python의 sorted() 함수를 사용하면 쉽게 정렬할 수 있습니다.

3단계: 파일 추가 및 합산

정렬된 파일 리스트를 순회하면서 현재 파일을 블루레이에 추가하였을 때, 전체 용량이 C를 초과하는지 확인합니다. 초과하지 않는 경우, 현재 파일을 블루레이에 추가하고 파일의 개수를 세어줍니다.

4단계: 결과 출력

모든 파일을 순회한 후 최종적으로 담길 수 있는 파일의 개수를 출력합니다.

5단계: 전체 코드


def maximum_files_in_blu_ray(capacity, files):
    # 파일 크기 정렬
    files.sort()
    count = 0
    total_size = 0

    for file in files:
        if total_size + file <= capacity:
            total_size += file
            count += 1
        else:
            break

    return count

# 입력 받기
capacity, n = map(int, input().split())
files = list(map(int, input().split()))

# 함수 호출 및 결과 출력
result = maximum_files_in_blu_ray(capacity, files)
print(result)

예제 입력 및 출력

예제 1

입력:

10 5
1 2 3 4 5

출력:

예제 2