[백준] 12865번: 평범한 배낭( 파이썬, 쉬운 설명, 코린이 버전 ) *비범한 배낭 주의

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 매우 매우 매우 매우 어려운 문제였습니다. 저한테는.

문제 제목이 매우 역설적으로 자괴감 느끼게 하고 ㅋㅋㅋ 누가 이게 디피의 전형적인 문제라고 해서 더 자괴감을 느꼈습니다.

 하지만, 자괴감을 느끼는 것도 이제 익숙해서, 저항이 생겨가네요.

많은 시간을 들여서, 결국 이해를 하고 여러분에게 전달드립니다.

 

 

< 코린이를 위한 쉽게 설명한 핵심 아이디어 > 

1. 우선 이분의 설명을 읽고 와 주세요 !! 정말 설명을 차근 차근 잘 해주셨더라구요.

suri78.tistory.com/2

[백준알고리즘] 12865번: 평범한 배낭 -Python

2. 저는 1번 자료에 조금 더 직관적인 설명을 덧붙이겠습니다.

확대해서 확인하시면, 설명이 더 직관적으로 다가올 거에요.

 

 

밑의 코드는 위에 나오는 아이디어를 코드로 표현한 겁니다.

조금 자세히 썼습니다.

#
n, k = map(int, input().split())

# 아이템의 인덱스 - (무게, 가치) 튜플 사전
dic = {} 
for i in range(n) :
    w, v = map( int, input().split() )
    dic[i] = (w, v)

print(dic)
# {0: (6, 13), 1: (4, 8), 2: (3, 6), 3: (5, 12)}


# 칼럼의 경우 무효칸을 맨 앞에 삽입하여, 칼럼 값이 실제 무게와 같이 형성되게 만듬
lst = [ [0] * (k+1) for _ in range(n) ]

# lst
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0]
    
# dynamic programming 을 위해, 첫 번째 행 설정
firstTuple = dic[0]
firstW, firstV = firstTuple

# 첫번째 칼럼 1 ~ 무게 한도까지 값 초기화
for i in range(1, k+1) :
    if firstW <= i :
        lst[0][i] = firstV
    else :
        lst[0][i] = 0

# lst
# [0, 0, 0, 0, 0, 0, 13, 13]
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0]


# dynamic programming 실시
    # 이번 항목을 포함할 수 없다면, 이전 항목을 포함한 것 까지의 최댓값 취하기
    # 이번 항목을 포함할 수 있다면
        # 1. 할 수 있어도 하지 않은 경우
        # 2. 포함하고, 정해진 무게한도로부터, 이번 항목의 무게를 제외하고, 이전 항목까지의 해당 무게 시의 최댓값 
            # : value + lst[r-1][c-weight]
            
for r in range(1,n) :
    weight, value = dic[r]
    for c in range(1,k+1):
        if weight <= c :
            lst[r][c] = max(
                              lst[r-1][c],
                              value + lst[r-1][c-weight]  
                                                            )
        else :
            lst[r][c] = lst[r-1][c]
        
# lst 
#[[0, 0, 0, 0, 0, 0, 13, 13],
#[0, 0, 0, 0, 8, 8, 13, 13],
#[0, 0, 0, 6, 8, 8, 13, 14],
#[0, 0, 0, 6, 8, 12, 13, 14]]

# dp array의 마지막 엔트리 프린트
print( lst[-1][-1] )