[백준] 12865 : 평범한 배낭 파이썬

문제 - https://www.acmicpc.net/problem/12865

생각보다 어려운 문제였습니다. 처음 제 힘으로 풀지 못했고, 풀이를 검색하여 이해하는데도 꽤나 오랜 시간이 걸렸습니다. 꽤 유명한 문제라고 알고 있는데 이해를 할 수 있게되어 다행이라 생각했습니다.

( 참고블로그 - https://claude-u.tistory.com/208 )

풀이

• 일단 물건 개수 * 무게 개수의 배열을 준비합니다.
• 그 배열에 각 물건을 집어 넣으며 모든 무게 별로 최대의 가치를 계산하여 더해갑니다.
• 해당 배열의 마지막 인자가 최대 가치를 가진 값이 됩니다..? 글로 설명하려니 조금 어렵습니다. 코드와 함께 설명을 더해보겠습니다.

code

#데이터 입력받기
n, k = map(int, input().split()); 
data = [];		#물건들의 무게, 가치를 담아줄 data 배열
data.append([0]); 	#index를 1부터 시작하게 하기 위해 데이터를 먼저 하나 추가해 줍니다.

#위에서 입력받은 물건의 개수인 n 만큼 반복하여 담아줍니다.
for _ in range(n):
    data.append(list(map(int, input().split())));

#모든 경우를 계산하기 위해 물건 개수 * 무게의 값을 가지는 form을 만들어 줍니다.
form = [[0 for _ in range(k+1)] for _ in range(n+1)];


#물건을 하나씩 담으며 가치를 계산합니다.
for i in range(1, n+1):
    for j in range(1, k+1):
        w = data[i][0];	#i번째 물건의 무게입니다.
        v = data[i][1]; #i번째 물건의 가치입니다.
        
        #핵심 부분입니다.
        #j<w부분에서는 이전 form[i-1]에 있었던 값을 그대로 가져와 입력을 해줍니다.
        #j>=w부분에서는 이번 물건의 가치 + form[i-1][j-w](남은 무게 만큼의 가치를 가지늠 물건이 있을 경우 해당 물건의 가치) 를 계산하여 입력을 해줍니다.
        if j<w:
            form[i][j] = form[i-1][j];
        else:
            form[i][j] = max(v+form[i-1][j-w], form[i-1][j]);
            
   #해당 print를 실행해보면 아래 이미지와 같은 데이터를 확인할 수 있습니다.
   #이해하는데 도움이 될 수 있습니다.
   print(form); 

print(form[-1][-1]);

코드는 짧은편에 어려운 기능도 사용되지 않았지만 이해를 하는데 조금 오래 걸렸던 문제입니다. 그러나 머리 회전에 도움을 주었던 문제였던 것 같습니다.