638. Shopping Offers
https://leetcode.com/problems/shopping-offers/
문제
풀이(DFS)
Example1을 기준으로 DFS 탐색 그래프를 그리면 다음과 같다.
즉 처음 탐색할 때 (depth = 1)일 때 No special(스페셜을 사지 않을 때)와 speical1(speical1을 살 때, 조건은 need가 음수면 안됨), special2(special2를 살 때, 조건은 need가 음수면 안됨)으로 탐색 할 수 있다. 여기서 중요한 점은 special을 탐색할 때 need가 음수인지 확인을 해야하는데 need => [3, 2]이고 speical은 [3,0]이다. 즉 need => [0, 2]가 되므로 음수가 되지 않아 탐색할 수 있다.
이제 special1에서 두번 째 탐색(depth = 2)을 확인해봐야하는데 마찬가지로 고를 수 있는 경우의 수는 No speical(스페셜을 사지 않을 때), Cant special1(speical을 사면 need가 음수가 됨), cant speical2(special2를 사면 need가 음수가 됨)으로 나눌 수 있는데 cant speical은 더 이상 탐색할 수 없다는 의미와도 같으므로 No speical값인 10을 리턴해준다.
이제 special2에서 세 번째 탐색(depth = 2)를 확인해 봐야하는데 No speical(스페셜을 사지 않을 때), Cant special1(speical을 사면 need가 음수가 됨), cant speical2(special2를 사면 need가 음수가 됨)으로 나눌 수 있는데 cant speical은 더 이상 탐색할 수 없다는 의미와도 같으므로 No speical값인 4을 리턴해준다.
이렇게 탐색 후 min(16,15,14) = 14가 답이 된다.
num 초기 값으로 No special(스페셜을 사지 않을 때)값을 저장한다. 이제 스페셜을 살 수 있는지 없는지 확인하고 살 수 있으면 또 다음을 탐색하는 구조이다.
결과(DFS)
배운점
처음에 작성했던 코드인데 인자를 리스트로 넘겨 주었다. 하지만 Cache는 리스트를 저장하지 못하였고, 해결하는 방법을 찾아보았다.
즉 dictionary, set, list같이 mutable한 자료형은 캐싱할 수 없고 immutalbe한 자료인 tuple로는 캐싱을 할 수 있다는 것이다. 그래서 튜플로 넘겨주고 계산하는 작업에는 리스트로 바꾼 후 다시 튜플로 넘겨주는 방법으로 해결하였다.
