1774. Closest Dessert Cost
https://leetcode.com/problems/closest-dessert-cost/
문제
문제를 설명하면 baseCosts에서 무조건 하나만을 선택해야 한다.
Example1에 baseCosts에서 1을 선택한다면 이제 toppingCosts를 선택해야 한다.
toppingCosts는 baseCosts와 다르게 선택해도 되고 선택안해도 된다. 하지만 2개 이상 선택할 수 없다. 즉 toppingCosts에 3을 3개를 선택할 수 없고 2개 이하만 선택 가능하다는 것이다.
baseCosts = 1, toppingCosts = 3x2 + 4x0 => 7
baseCosts = 1, toppingcosts = 3x1 + 4x1 => 8
baseCosts = 1, toppingCosts = 3x0 + 4x2 => 9 등등 나올 수 있고 총 합계가 target에 가장 가까운 수를 찾는 것이다.
풀이(Recursion)
DFS 트리 구조 그림이다. Example1 예제로 설명하였고 baseCosts = 1일 때이다.
그래프에는 1만 보여주었지만 2일 때에도 계산하여야 한다. target = 10이므로 baseCosts = 1을 계산하면 10-1 = 9가 된다.
그 후 [0,1, 2] => 최대 2개 까지 선택가능 함, 선택 안 할 수도 있음
개수만큼 toppingCosts를 계산한다. 토핑을 아무것도 선택안 할때에는 9-3x0, 하나만 선택할 때에는 9-3x1, 두개만 선택할 때에는 9-3x2가 된다.
그 후 [0,1,2]만큼 그 다음 토핑을 계산한다, 그래프에서 맨 아래 자식노드와 같이 되는데 여기서 키포인트가 있다. 절대값을 계산해서 최소값을 리턴해주어야 하지만 그 중에서도 양수값을 리턴해주어야 한다. 그래프를 보게 되면 [9-3*1] 자식 노드들 중에서 [6-4*1], [6-4*2]노드가 있을 것이다. 이 값은 각각 2, -2를 리턴하는데 절대값은 2로 같다. 하지만 리턴할 때에는 2를 해주어야 하는데 그 이유는 조건에서 여러개 있을 시 낮은 값을 리턴하라고 명시하였기 때문이다.
이렇게 절대값 중 최소값을 리턴하되 양수값을 리턴해주면 된다.
결과(Recursion)
