✍️ 문제 2-2
제7회 소프트웨어(SW) 사고력 올림피아드(초5~6)
※ 다음 문제에 답하시오.
※ 답은 종이에 작성한 뒤 사진으로 제출하세요.
※ 창의적인 생각을 자유롭게 기록해도 됩니다.
문제 2
알리바바는 배낭여행 중 보물 동굴을 발견했다. 보물 동굴 안에는 4개의 보물이 있었고 각 보물은 무게와 가치가 다르다. 알리바바가 가지고 간 배낭에는 최대 10kg까지만 담을 수 있다.
보물 A, B, C, D의 무게와 가치를 비교하여 답하시오.
문제 2-2
1)을 통해 배낭에 넣을 수 있는 최대가치를 구할 수 있다. 이 방법보다 더 간단하고 쉽게 최대가치를 구하는 방법을 생각해서 제시하시오.
[문제 분석]
무게와 가치가 있는 보물 조합을 10kg 제한 안에서 비교해 최대 가치를 찾는 최적화 문제입니다.
[예시답안 요약 힌트]
가능한 조합을 먼저 나열하고 무게 제한을 넘는 조합을 제외하세요. 가치/무게 비율이나 동적 비교 방법을 쓰면 최대값을 더 쉽게 찾을 수 있습니다.
더 간단하게 최대가치를 구하는 방법 (단위 무게당 가치 기준 정렬):
각 보석의 kg당 가치를 계산한다:
D: 50만/3kg = 16.7만원/kg
C: 30만/2kg = 15.0만원/kg
B: 40만/4kg = 10.0만원/kg
A: 10만/5kg = 2.0만원/kg
가치가 높은 순서대로 배낭에 담는다: D(3kg) → C(2kg) → B(4kg) = 총 9kg, 120만원.
이 방법(그리디 알고리즘)은 단위 가치가 높은 것부터 채우기 때문에 모든 조합을 확인하지 않아도 빠르게 최적값을 구할 수 있다.
아직 등록된 참가자 답안이 없습니다.
로그인 후 답안을 작성할 수 있습니다.