코딩 테스트 12865번 - 파이썬

📢

문제에 풀기 앞서서 
코딩테스트를 문제를 풀어감에 있어서 문제 식별 문제 풀이 과정을 어떻게 할지, 코딩, 시간 복잡도, 공간복잡도 그리고 최적화가 가능한 방법이 있지 않을까에 대한 고찰 등으로 진행할 예정입니다. 이 문장은 모든 문제에 제일 상단에 위치할 예정입니다. 

 

먼저 문제를 확인해보면 두가지 문제가 있다고 볼수있다. 먼저, 무게를 상한선을 지켜야 한다. 또한, 최대의 가치를 가져야 한다. 따라서이문제는 DP방식으로 사용해야한다. 

2차배열로 사용해서 진행을 해보면 쉽게 해결될것이라고 생각한다.

 

먼저,초기 세팅을 해야하는 걸로 받는다 그리고 이에 대해 tuple로 이용해서 저옵들을 저장한다. 그리고 dp관련 2차배열을 만들고 이에 따라 2차배열로 dp이용 반복문을 만든다. 

 

n, k = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

# 2차원 DP 테이블
dp = [[0] * (k + 1) for _ in range(n + 1)]

# DP 채우기
for i in range(1, n + 1):
    w, v = items[i - 1]
    for j in range(k + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

print(dp[n][k])

 

이와 같이 만든다 그러면 시간 복잡도는 N^2 공간 복잡도는 n*k가 된다. 이에 따라 진행하면 될듯하다. 
여기서 는 1차배열로 바꿀수있다고 하는데 1차배열이 빠를수는 있으나 로깅이나 중간 체크가 어렵다는 단점이 있다. 물론 코딩테스트에서는 없는게 나을수도있지만 직접 구현할때는 사용하지 않을 듯 싶으니 넘어갈까 한다.