인프런 커뮤니티 질문&답변

2022 KAKAO TECH INTERNSHIP 문제 중 코딩테스트 공부 문제에서 실패하는 경우가 있어서 왜 그런지 질문드리려고 합니다. 예시풀이 중 dp풀이랑 비슷하게 풀었는데 다른 점은 저는 dp[alg][cop]을 해당 alg, cop에 도달하기 위해 필요한 최소 비용으로 정의하고 마지막에 최대 alg~+30, co~ +30 중 최소값을 리턴하도록 정의했습니다. 이렇게 하니까 정확성은 다 통과하는데 효율성에서 실패하는 경우가 생기던데 왜그럴까요?

def solution(alp, cop, problems):
    answer = 0
    problems += [[0,0,1,0,1], [0,0,0,1,1]]
    dp = [[1000] * 181 for _ in range(181)]
    dp[alp][cop] = 0
    goal = [alp,cop]
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        goal[0] = max(goal[0], alp_req)
        goal[1] = max(goal[1], cop_req)
    for i in range(alp, 181):
        for j in range(cop, 181):
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if i >= alp_req + alp_rwd and j >= cop_req + cop_rwd:
                    dp[i][j] = min(dp[i][j], dp[i-alp_rwd][j-cop_rwd] + cost)
    answer = 1000
    for row in dp[goal[0]:]:
        answer = min(answer, min(row[goal[1]:]))
    
    
    return answer