[TIL] - 2023.04.28

📌 - G5_12865_평범한 배낭 문제

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

DP문제를 풀기 시작했는데, 계속 머리를 굴려봐도 풀이법이 생각나지 않아서 다른 사람들 풀이를 참고했다.

 

이때까지는 2차원 배열을 컨트롤 할 때 i,j를 이용해서 i,j의 값에 맞는 칸을 업데이트 시켜주는 느낌이었는데,

 

DP는 여러 문제들을 보다보니 i,j로 컨트롤 하긴 하지만 , 아래의 예시와 같이 j를 가방의 무게인 w와 비교해서 해당하는 칸에 i,j 뿐만 아니라  w, v와 같은 변수들까지 같이 사용해야돼서 그런지 이해가 잘 안된다. 

 

아래의 예시에도 j와 w를 비교해서 j가 w보다 작으면 이전 값을 가져와서 업데이트 해주고,

j가 w와 같거나 크다면 이전 가방과 현재 가방의 무게로 만들 수 있는 값을 업데이트 해주는 방법을 사용한다.

 

아래의 코드를 표로 그려봄

🔥 - 파이썬 코드

from sys import stdin as s
from collections import deque

s = open('input.txt','rt')
# 4 7
# 6 13
# 4 8
# 3 6
# 5 12 의 데이터를 입력

n, k = map(int, s.readline().split())


thing = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    thing.append(list(map(int, s.readline().split())))

for i in range(1, n+1): # i -> 다른 짐
    for j in range(1, k+1): # j -> 허용되는 무게
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])

 

 

 

 

---

 

 

 

「 신의 섭리를 탓하고 싶을 때마다 자네의 마음 주변을 살펴보게. 그러면 어떤 이유로 그 일이 일어났는지 알 수 있을 것이야. 」

-에픽테토스, 대화록 3.17.1

 

무언가 잘못되었다는 느낌은 단지 인식의 문제일 뿐이다. 모든 일에 이유가 있겠지만 한 개인이 광대한 섭리의 이면을 정확하게 파악하기는 힘들다.

지구 반대편에 있는 나비의 작은 날갯짓 때문에 태풍이 발생할 수도 있고 지금 겪고 있는 불운이 행운의 전조일 수도 있다.

 

「 제논은 지식을 확고하게 이해하기 위해서 자기기만을 가장 경계해야 한다고 말했다. 」

-디오게네스의 강의, 탁월한 철학자들의 삶. 7.23

 

자신이 이미 완벽하며 널리 존경받는다고 생각하는 한 우리는 어떤 덕성도 함양할 수 없으며 타인의 존경을 얻는 것도 불가능하다. 그런 의미에서 그릇된 자부심과 자기기만은 인간이 마땅히 가져야하는 미덕의 적이다.

이 둘은 무엇이든 '이미 갖고 있다'라며 우리를 속인다. 그러므로 우리는 우리를 속이기 위해 기민하게 달려오는 자부심을 적대하는 마음으로 대해야 한다.

항상 겸손하고, 성찰하며 반성하는 자세로 삶을 대해야 시야가 넓어지며 견문이 생긴다.

 

「 3천 년을 살아간다고 할지라도, 헤아릴 수 없이 많은 인생을 살 수 있다고 할지라도 명심하라. 우리가 잃어버리는 것은 현재 우리가 영위하고 있는 순간의 삶이며 소유할 수 있는 것 또한 지금 이 순간의 삶뿐이다. 긴 삶이든 짧은 삶이든 동일하다. 우리 모두가 소유할 수 있는 것은 지금 스쳐 지나고 있는 현재밖에 없다. 과거를 잃어버리거나 미래를 잃어버릴 수는 없다. 어떻게 지금 갖고 있지 않은 것을 잃어버릴 수 있겠는가? 」

-마르쿠스 아우렐리우스, 명상록, 2.14

 

"어제는 지나간 과거요, 내일은 다가올 미래지만, 오늘은 선물이다. 우리가 현재(present)를 선물(present)이라고 부르는 이유도 여기에 있다."

우리는 현재만을 소유한다. 그 현재에도 만료일은 있다. 그것도 만료일이 너무 빨리 다가온다. 그래서 현재를 즐겨야 한다. 이것만이 우리 전 생애를 통해 지속되는 것이다.

하루는 너무나도 짧고 현재는 매 순간 지나간다. 현재를 즐기고, 건강하게 소비를 하는 것이 지나간 과거와 다가올 미래에 대한 예의이다.

 

---

 

🔥 - 토끼 다 키우고 싶었는데 집중이 너무 안돼서 실패.. 오늘은 일찍 쉬고 내일 일찍나와서 더 열심히 하기