https://school.programmers.co.kr/learn/courses/30/lessons/172927

---

1. 코드

def solution(picks, minerals):
    def dfs(idx, dcnt, icnt, scnt, path):
        if dcnt > picks[0] or icnt > picks[1] or scnt > picks[2]:
            return

        if idx == N:
            cnt = 0
            for i in range(0, N * 5, 5):
                chunk = minerals[i:i + 5]
                if not chunk:
                    break
                for m in chunk:
                    if m == 'diamond':
                        cnt += fatigue[path[i//5]][0]
                    elif m == 'iron':
                        cnt += fatigue[path[i//5]][1]
                    else:
                        cnt += fatigue[path[i//5]][2]
                    # 가지치기
                    if cnt > ans[0]:
                        return
            ans[0] = min(ans[0], cnt)
            return
		# N이 최대 15일 경우 3^15번 호출
        dfs(idx + 1, dcnt + 1, icnt, scnt, path + ['d'])
        dfs(idx + 1, dcnt, icnt + 1, scnt, path + ['i'])
        dfs(idx + 1, dcnt, icnt, scnt + 1, path + ['s'])

    fatigue = {'d': (1, 1, 1),
               'i': (5, 1, 1),
               's': (25, 5, 1)
               }
    N = sum(picks)
    ans = [float('INF')]
    dfs(0, 0, 0, 0, [])
    return ans[0]

---

2. 후기

[백준] Gaaaaaaaaaarden 문제와 동일하게 풀었다.

dfs의 가지치기를 제외한다고 생각하면 최대 3^15번의 호출이 발생한다. 3^15는 대략 O(14,000,000)정도이므로 아슬아슬하게 풀 수는 있을 것 같다는 생각으로 접근했다.

dfs의 파라미터로 answer를 사용는 풀이로 바꾼다면 answer보다 값이 큰 경우 idx가 N에 도달하기 전에 가지치기를 통해 백트래킹 할 수 있으므로 훨씬 빨리 풀 수 있을 것 같다.