[Python][Programmers]완전범죄

문제 링크

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

 

문제 냄새가 딱 DP였다.

백트래킹으로 풀이할 수도 있었을 것 같은데 모든 경우를 세어주는데 메모리적으로 문제가 있을 것 같았다.

오히려 2차원 배열을 만들어서 관리하는게 배열의 길이가 그렇게 길지 않아 디버깅이나 풀이에 더 편할 것 같았다.

 

작성 코드는 아래와 같이 작성했다.

def solution(info, n, m):
    INF = float("inf")
    
    info_length = len(info)
    DP = [[INF] * m for _ in range(info_length + 1)]

    DP[0][0] = 0
    for i in range(1, info_length + 1):
        a, b = info[i-1][0], info[i-1][1]
        for j in range(m):
            DP[i][j] = min(DP[i][j], DP[i-1][j] + a)

            if j + b < m:
                DP[i][j+b] = min(DP[i][j+b], DP[i-1][j])
    min_value = INF
    for x in range(m):
        min_value = min(DP[info_length][x], min_value)
    
    if min_value >= n: result = -1
    else: result = min_value
    
    return result

 

2중 for문을 돌리기에 시간복잡도가 그렇게 높지 않아서 DP 연산으로 처리하면 될 것 같았다.

2차원 배열로 충분히 풀이할 수 있는 문제였다. 백준으로 따지면 실버 2 ~ 1 정도 되는 DP 문제였던 것 같다.

(DP 문제들은 해결점이 워낙 안떠올라서)

 

오랜만에 DP도 풀고, 프로그래머스에서 풀이해서 좋았다.

최적화 문제를 해결하기 위해서는 DP 문제를 많이 풀어봐야할 것 같아서 풀이했다.