코딩 테스트 공부

문제 설명 및 제한사항

아이디어 및 해결 방법


from collections import namedtuple from heapq import heappush, heappop from math import inf Problem = namedtuple('Problem', ['cost', 'areq', 'creq', 'arwd', 'crwd']) def solution(alp, cop, problems): dist, visited, q = {(alp, cop): 0}, set(), [] problems = [Problem(cost, areq, creq, arwd, crwd) for areq, creq, arwd, crwd, cost in problems] problems += [Problem(1, 0, 0, 1, 0), Problem(1, 0, 0, 0, 1)] maxareq = max(p.areq for p in problems) maxcreq = max(p.creq for p in problems) heappush(q, (0, alp, cop)) while len(q) > 0: d, a, c = heappop(q) if (a, c) in visited: continue else: visited.add((a, c)) for p in problems: newa, newc = min(a+p.arwd, maxareq), min(c+p.crwd, maxcreq) newcost = d + p.cost if a >= p.areq and c >= p.creq and newcost < dist.get((newa, newc), inf): dist[(newa, newc)] = newcost heappush(q, (d + p.cost, newa, newc)) return dist[(maxareq, maxcreq)]


프로그래머스 코딩테스트 연습