문제 개요
두 개의 정수 tomatoSlices(토마토 슬라이스 수)와 cheeseSlices(치즈 슬라이스 수)가 주어집니다. 이 재료들은 서로 다른 종류의 버거를 만드는 데 사용됩니다.
- 점보 버거(Jumbo Burger): 토마토 슬라이스 4개와 치즈 슬라이스 1개 필요
- 스몰 버거(Small Burger): 토마토 슬라이스 2개와 치즈 슬라이스 1개 필요
목표는 [점보 버거 수, 스몰 버거 수] 형태의 조합을 찾아, 버거를 만든 뒤 남는 토마토 슬라이스와 치즈 슬라이스가 모두 0이 되도록 하는 것입니다. 만약 주어진 재료를 전부 사용할 수 있는 조합이 존재하지 않는다면 빈 배열 []을 반환해야 합니다.
예를 들어 입력이 tomatoSlices = 16, cheeseSlices = 7이라면 출력은 [1, 6]입니다. 이는 점보 버거 1개와 스몰 버거 6개를 만들면 토마토 슬라이스가 4×1 + 2×6 = 16개, 치즈 슬라이스가 1 + 6 = 7개로 재료가 정확히 소진된다는 의미입니다.
접근 방법
이 문제는 간단한 연립방정식으로 모델링할 수 있습니다. 점보 버거의 수를 j, 스몰 버거의 수를 s라고 하면 다음 두 식이 성립합니다.
- 4j + 2s = tomatoSlices
- j + s = cheeseSlices
이 방정식을 풀면 스몰 버거의 수는 s = (4 × cheeseSlices − tomatoSlices) / 2, 점보 버거의 수는 j = (tomatoSlices − 2 × s) / 4로 계산할 수 있습니다.
단, 다음 세 가지 경우에는 유효한 조합이 존재하지 않으므로 빈 배열을 반환해야 합니다.
- 토마토 슬라이스 수가 홀수인 경우: 버거 하나당 토마토는 4개 또는 2개씩 소모되므로, 사용되는 토마토의 총량은 항상 짝수입니다.
- cheeseSlices > tomatoSlices / 2인 경우: 모든 버거를 스몰 버거로 만들더라도 치즈 하나당 최소 토마토 2개가 필요하므로 토마토가 부족합니다.
- tomatoSlices > 4 × cheeseSlices인 경우: 모든 버거를 점보 버거로 만들어도 치즈 하나당 최대 토마토 4개까지만 사용할 수 있으므로 토마토가 남게 됩니다.
전체적인 해결 절차는 다음과 같습니다.
- 결과를 담을 배열 ans를 생성합니다.
- 토마토 수가 홀수이거나, 치즈 수 > 토마토/2 또는 토마토 수 > 치즈×4이면 빈 배열을 반환합니다.
- x := (4 × cheese − tomato) / 2 (스몰 버거 수)
- y := (tomato − 2 × x) / 4 (점보 버거 수)
- y, x 순서대로 ans에 삽입합니다.
- ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> numOfBurgers(int t, int c) {
vector <int> ans;
if(t % 2 != 0 || c > t/2 || t > c*4)return ans;
int x = (4 * c - t) / 2;
int y = ( t - (2 * x) )/ 4;
ans.push_back(y);
ans.push_back(x);
return ans;
}
};
main(){
Solution ob;
print_vector(ob.numOfBurgers(16,7));
}
실행 결과
입력
16
7
출력
[1, 6]
출력 결과 [1, 6]은 점보 버거 1개와 스몰 버거 6개를 만들면 모든 재료가 낭비 없이 사용된다는 것을 보여줍니다. 이 알고리즘은 단순한 산술 연산만으로 정답을 구하므로 시간 복잡도는 O(1)이며, 매우 효율적입니다.