일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 백준 12761번
- http 개념
- go
- 우분투
- hadoop
- flask
- golang
- 자바
- String 함수
- 백준
- golang struct
- 백준 사이트
- http 완벽가이드
- 백준 12761
- 파이썬
- 자바 디자인패턴
- 12761번 돌다리
- 고 배열
- 하둡
- 트리 순회
- 몽고디비 렘
- 자바 디자인 패턴
- 12761 돌다리
- 도메인 주도 개발 시작하기
- 도메인 주도 개발
- 백준 파이썬
- domain driven develop
- 정렬
- ddd
- MongoDB Realm
- Today
- Total
개발바닥
BOJ_12865 [ 평범한 배낭 ] [ 파이썬 ] 본문
문제
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
문제 해결 방법
다이나믹 프로그래밍으로 문제를 해결해야 된다.
첫번째 물건부터 시작해서 현재 물건을 넣었을 때와 넣지 않았을 때 가치 중 큰 값을 갱신해주면 된다.
물건을 넣었을 때와 넣지 않았을 때를 어떤식으로 코드를 구현해야 될까요?
통과한 코드를 분석해보면 다음과 같다.
for i in 물건개수 :
for j in 1부터 K까지 무게:
if 해당 물건 인덱스 무게가 j 보다 작거나 같다면 현재 물건을 넣을 수 있다. (여기서 넣을지 말지 판단을 하게 된다.)
dp[i][j] = max ( dp[i-1][j] (현재 물건을 안넣은 경우) , dp[i-1][j - w ] + v (현재 물건을 넣은 경우 현재 물건을 뺀 무게 중 가치가 가장 큰 값 + 현재 아이템 가치)
else j 무게 중 제일 큰 값을 대입
dp[i][j] = dp[i-1][j]
소스 코드 보기
https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_12865.py
jokerKwu/BOJ_Algorithm
Contribute to jokerKwu/BOJ_Algorithm development by creating an account on GitHub.
github.com
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
dp = [ [0]*(K+2) for _ in range(N+1) ]
weight = []
value = []
weight.append(0)
value.append(0)
for i in range(1, N+1):
w, v = map(int, input().split())
weight.append(w)
value.append(v)
for i in range(1, N+1):
for j in range(1, K+1):
if j >= weight[i]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[N][K])
'[ Algorithm ] > [ PYTHON ]' 카테고리의 다른 글
BOJ_14395 [ 4연산 ] [ 파이썬 ] (1) | 2020.06.29 |
---|---|
BOJ_14002 [ 가장 긴 증가하는 부분 수열 4 ] [ 파이썬 ] (0) | 2020.06.19 |
BOJ_11058 [ 크리보드 ] [ 파이썬 ] (0) | 2020.06.10 |
BOJ_2864 [ 5와 6의 차이 ] [ 파이썬 ] (0) | 2020.06.01 |
BOJ_12761 [ 돌다리 ] [ 파이썬 ] (0) | 2020.05.29 |