이 문제에서는 두 개의 배열이 주어집니다. 하나는 베이스(아이스크림 기반)의 가격을 담은 baseCosts(n개 요소)이고, 다른 하나는 토핑의 가격을 담은 toppingCosts(m개 요소)입니다. 그리고 목표 가격을 나타내는 target 값도 함께 주어집니다.
디저트를 만들 때는 아래 규칙을 반드시 따라야 합니다.
- 베이스는 정확히 하나만 선택해야 합니다.
- 토핑은 하나 이상 추가하거나, 아예 추가하지 않아도 됩니다.
- 각 종류의 토핑은 최대 2개까지 사용할 수 있습니다.
여기서 baseCosts[i]는 i번째 아이스크림 베이스의 가격, toppingCosts[i]는 i번째 토핑 하나의 가격을 의미합니다. 우리의 목표는 전체 비용이 target에 최대한 가까운 디저트를 만드는 것이며, 그때의 가장 가까운 비용을 구해야 합니다. 만약 답이 여러 개라면 더 낮은 쪽의 비용을 반환합니다.
문제 예시
예를 들어 baseCosts = [2, 8], toppingCosts = [4, 5], target = 12라고 입력이 주어졌다고 가정해 봅시다. 이 경우 출력은 12가 됩니다. 그 이유는 비용이 8인 베이스를 선택하고, 첫 번째 토핑(비용 4)을 1개 추가한 뒤 두 번째 토핑은 사용하지 않으면 총 비용이 8 + 4 = 12로 목표값과 정확히 일치하기 때문입니다.
해결 접근 방법
이 문제는 완전 탐색(Brute Force) 방식으로 해결할 수 있습니다. 각 베이스마다 모든 토핑 조합을 확인하는 것입니다. 토핑은 각 종류당 0개, 1개, 2개 중 하나로 사용할 수 있으므로, bitmask 배열을 활용해 가능한 모든 조합을 순회하며 다음 단계를 수행합니다.
- 최적 비용(best_cost)을 baseCosts[0]으로 초기화합니다.
- 각 베이스 b에 대해 bitmask 배열(모든 값을 0으로 초기화)을 생성합니다.
- 현재 가격(current_price)을 계산하고, target과의 차이가 0이면 즉시 target을 반환합니다.
- |current_price - target|이 |best_cost - target|보다 작으면 best_cost를 갱신합니다.
- 절대값 차이가 같다면, 더 낮은 가격으로 best_cost를 갱신합니다.
- bitmask의 모든 값이 2가 되면 해당 베이스의 탐색을 종료하고, 다음 베이스로 넘어갑니다.
모든 경우를 확인한 후 최종적으로 best_cost를 반환하면 됩니다.
구현 예제 코드
아래는 위 알고리즘을 Python으로 구현한 코드입니다.
def solve(baseCosts, toppingCosts, target):
best_cost = baseCosts[0]
for b in range(len(baseCosts)):
bitmask = [0] * len(toppingCosts)
while True:
current_price = baseCosts[b]
for j in range(len(bitmask)):
current_price += bitmask[j] * toppingCosts[j]
if current_price - target == 0:
return target
elif abs(current_price - target) < abs(best_cost - target):
best_cost = current_price
elif abs(current_price - target) == abs(best_cost - target):
if current_price < best_cost:
best_cost = current_price
if 0 not in bitmask and 1 not in bitmask:
break
for i in range(len(bitmask)):
if bitmask[i] != 2:
bitmask[i] += 1
break
else:
bitmask[i] = 0
return best_cost
baseCosts = [2,8]
toppingCosts = [4,5]
target = 12
print(solve(baseCosts, toppingCosts, target))입력
[2,8], [4,5], 12
출력
12
마무리
이 프로그램은 각 베이스와 토핑 조합의 모든 경우의 수를 탐색하여 목표 가격과 가장 가까운 디저트 비용을 찾습니다. 토핑의 개수가 적을 때 효율적으로 동작하며, 목표 가격과 정확히 일치하는 조합을 발견하면 즉시 결과를 반환해 불필요한 연산을 줄일 수 있다는 장점이 있습니다.