RETROSPECTIVE · 회고
쿠폰 최적 조합: 어려운 문제라도 완전탐색이 답일 때
Algorithm
주문서에서 "할인 금액이 가장 큰 쿠폰 조합"을 자동으로 골라주는 기능을 검토했다. 조건은 이렇다.
- 쿠폰마다 적용 가능한 상품 조건이 다르다.
- 한 상품에는 쿠폰 한 장, 쿠폰도 한 번만 쓸 수 있다.
- 주문 전체에 거는 쿠폰은 "다른 쿠폰 적용 후 금액이 N원 이상" 같은 조건이 붙는다.
모델링하면
상품 쿠폰만 있다면 쿠폰–상품 이분 그래프의 최대 가중치 매칭이라 헝가리안 알고리즘으로 다항 시간에 풀 수 있다. 문제는 주문 쿠폰이다. 상품 쿠폰을 어떻게 쓰느냐에 따라 주문 금액이 바뀌고, 그게 다시 주문 쿠폰의 사용 가능 여부를 바꾼다. 조건이 서로 얽히면서 깔끔한 매칭 문제가 아니게 된다.
입력 크기를 먼저 봤다
이론적으로 어려운 문제여도 실제 입력이 작으면 완전탐색이 가장 정확하고 단순하다. 한 사람이 한 주문에 쓸 수 있는 쿠폰은 대부분 10장 이하였다. 쿠폰을 하나씩 보면서 "안 쓴다 / 적용 가능한 상품 중 하나에 쓴다"로 분기하는 백트래킹에, 남은 쿠폰으로 얻을 수 있는 최대 할인으로 가지치기를 붙였다.
function best(coupons: Coupon[], items: Item[], totalPrice: number) {
// 남은 상품 쿠폰 + 주문 쿠폰이 낼 수 있는 할인의 상한 (가지치기용)
const bound = suffixSum(coupons.map((c) => maxDiscount(c, items)));
const orderMax = maxOrderCouponDiscount();
let answer = 0;
const used = new Set<number>();
function dfs(i: number, sum: number) {
if (sum + bound[i] + orderMax <= answer) return; // 더 좋아질 수 없음
if (i === coupons.length) {
// 상품 쿠폰 적용 후 금액으로 주문 쿠폰 조건을 판단
answer = Math.max(answer, sum + orderCouponDiscount(totalPrice - sum));
return;
}
dfs(i + 1, sum); // 이 쿠폰은 안 씀
for (const it of items) {
if (used.has(it.id) || !applicable(coupons[i], it)) continue;
used.add(it.id);
dfs(i + 1, sum + discount(coupons[i], it));
used.delete(it.id);
}
}
dfs(0, 0);
return answer;
}
상한에 주문 쿠폰 몫(orderMax)을 빼먹으면 가지치기가 정답을 잘라낼 수 있어서, 상한은 항상 "실제로 가능한 값 이상"이 되도록 넉넉하게 잡았다.
결과와 안전장치
쿠폰 10장, 상품 20개 수준에서 수 ms 안에 끝났다. 그래도 입력이 비정상적으로 커질 때를 대비해 쿠폰 수가 기준을 넘으면 할인액 큰 순서의 그리디로 대체하도록 상한을 뒀다.
배운 점
"NP-hard니까 근사해야 한다"보다 먼저 실제 N이 얼마인지 확인하는 게 우선이다. 작은 N에서는 정확한 답을 주는 완전탐색이 설명하기도, 검증하기도 쉽다.