문제 개요
세 개의 숫자 a, b, c가 주어집니다. 각각 레몬 a개, 사과 b개, 배 c개를 의미합니다. 컴포트(compote, 설탕에 절인 과일)를 만들려면 과일의 비율이 반드시 1 : 2 : 4를 유지해야 하며, 과일을 잘라서 사용할 수는 없습니다. 이때 컴포트를 만드는 데 사용할 수 있는 레몬, 사과, 배의 최대 총 개수를 구하는 것이 목표입니다. 만약 어떤 과일 조합도 만들 수 없다면 0을 반환합니다.
예를 들어 입력이 a = 4, b = 7, c = 13이라면 출력은 21입니다. 레몬 3개, 사과 6개, 배 12개를 사용하면 정확히 1 : 2 : 4의 비율이 되고, 답은 3 + 6 + 12 = 21이 되기 때문입니다.
풀이 접근 방식
핵심 아이디어는 '세트' 단위로 생각하는 것입니다. 비율 1 : 2 : 4를 만족하는 한 세트는 다음과 같이 구성됩니다.
- 레몬 1개
- 사과 2개
- 배 4개
즉, 한 세트당 과일은 총 7개입니다. 각 과일로 만들 수 있는 세트 수를 계산해 보면 다음과 같습니다.
- 레몬으로 만들 수 있는 세트 수: a
- 사과로 만들 수 있는 세트 수: b ÷ 2 (정수 나눗셈, 즉 내림)
- 배로 만들 수 있는 세트 수: c ÷ 4 (정수 나눗셈, 즉 내림)
가장 부족한 과일이 전체 생산량을 제한하는 병목(bottleneck)이 되므로, 가능한 최대 세트 수는 이 세 값 중 최솟값입니다. 따라서 전체 과일 수는 최솟값에 7을 곱한 것이 됩니다.
return 7 * min(a, min(b / 2, c / 4));
만약 세 값 중 하나라도 0이라면 결과도 자연스럽게 0이 되므로, '만들 수 없는 경우 0 반환' 조건도 별도 처리 없이 함께 해결됩니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b, int c){
return 7 * min(a, min(b / 2, c / 4));
}
int main(){
int a = 4;
int b = 7;
int c = 13;
cout << solve(a, b, c) << endl;
}입력
4, 7, 13
출력
21
동작 원리 정리
입력 a = 4, b = 7, c = 13에 대해 코드는 다음과 같이 계산합니다.
- 레몬 기준 세트 수: 4
- 사과 기준 세트 수: 7 / 2 = 3
- 배 기준 세트 수: 13 / 4 = 3
세 값 중 최솟값은 3이므로, 최종 결과는 7 × 3 = 21이 됩니다. 이처럼 정수 나눗셈의 내림 특성과 최솟값 연산만으로 비율 제약 문제를 O(1) 시간에 간단하게 해결할 수 있습니다.