[LeetCode] 638. Shopping Offers

😎풀이

1. 순수 물건 구입으로 최소 금액 계산
2. 깊이 우선 탐색
   2-1. special 상품을 구입하거나 생략함
   2-2. 모든 special 상품을 확인하고 난 후 필요한 수량은 정가로 구입
   2-3. 최소 금액 갱신
3. 탐색 가능한 최소 금액 반환

function shoppingOffers(price: number[], special: number[][], needs: number[]): number {
    const specialLen = special.length
    let minPrice = needs.reduce((a, b, i) => a + b * price[i], 0)
    function dfs(remain: number[], curPrice: number, i: number) {
        if(i === specialLen) {
            const remainPrice = remain.reduce((a, b, i) => a + b * price[i], 0)
            minPrice = Math.min(minPrice, curPrice + remainPrice)
            return
        }
        const curSpecial = special[i]
        const remainNeeds = [...remain]
        let isValid = true
        for(let idx = 0; idx < price.length; idx++) {
            remainNeeds[idx] -= curSpecial[idx]
            if(remainNeeds[idx] < 0) {
                isValid = false
                break
            }
        }
        if(isValid) {
            dfs(remainNeeds, curPrice + special[i].at(-1), i)
        }
        dfs(remain, curPrice, i + 1)
    }
    dfs([...needs], 0, 0)
    return minPrice
};