배울점: 이 코드로 하면 시간 초과도 날 뿐더러 정확성도 보장할 수 없다. 저기 mx = max_x + 1000을 확실히 하려면 1000을 4500으로 바꿔줘야 한다. 왜냐하면 만약 max_x = alp여서 더이상 움직일 필요가 없는데 cop = 0인데 max_y=150이라고 가정해보자. 그리고 극단적으로 상황을 단순화하기 위해 x는 30만큼 늘고 y는 1만큼 느는 요소 밖에 존재하지 않는다고 가정하자. 그러면 총 150번의 iteration이 필요하고 이는 30150만큼의 공간이 더 필요하게 되는 형태가 된다. 물론 이러한 극단적인 경우는 존재하지 않는데 y가 2만큼 존재하고 cost가 1일때 다른 요소들은 동일하다고 하면 말이 된다. 그러면 3075만큼의 공간으로 2150만큼을 더해줘야 한다. 그런데 이렇게 하면 시간초과가 날 수밖에 없다. 따라서 이렇게 접근하면 안된다고 생각해야한다. 그래서 앞으로부터 접근하는 방법을 생각해야하는 것이다.

def solution(alp, cop, problems):
    INF = int(1e9)
    answer = INF
    problems.extend([[0, 0, 1, 0, 1], [0, 0, 0, 1, 1]])
    problems.sort(reverse=True)
    max_x = problems[0][0]
    problems.sort(key=lambda x: x[1], reverse=True)
    max_y = problems[0][1]

    mx = max_x + 1000
    my = max_y + 1000

    alp = min(alp, max_x)  # 둘중 하나라도 목표값을 넘어가면 안된다.
    cop = min(cop, max_y)
    #if max_x == alp:
    #    mx = alp + 30
    #if my - cop < 30:
    #    my = cop + 30
    d = [[INF] * (my + 1) for _ in range(mx + 1)]
    d[alp][cop] = 0

    for x in range(alp, mx + 1):
        for y in range(cop, my + 1):
            # HI(d,i, j, problems, alp, cop)
            INF = int(1e9)
            for p in range(len(problems)):
                cx = problems[p][0]
                cy = problems[p][1]
                dx = problems[p][2]
                dy = problems[p][3]
                cost = problems[p][4]
                nx = x - dx
                ny = y - dy

                if nx < cx or ny < cy:
                    continue
                #if nx < alp or ny < cop:
                #    continue
                #if nx >= max(max_x, alp) or ny >= max(max_y, cop):
                #    continue

                d[x][y] = min(d[x][y], d[nx][ny] + cost)

    #max_x = max(alp, max_x)
    #max_y = max(cop, max_y)
    for x in range(max_x, mx + 1):
        for y in range(max_y, my + 1):
            answer = min(d[x][y], answer)
    # answer=d[max_x][max_y]
    #debug(d)
    return answer