[백준(BOJ)] 1535번 : 안녕 - PYTHON[파이썬]

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

1535번: 안녕

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 브루트포스 알고리즘
• 배낭 문제

 

---

 

⊙ 문제 접근 과정

 

0-1 배낭문제 알고리즘으로 문제를 풀면 된다.

그냥 평범한 배낭 문제에서 변수명만 바꿔도 풀린다.

 

이전 최대가치와 이전 값을 빼고 현재 값을 넣은 것과 비교하여 더 가치가 높은 것을 넣어주자

 

---

 

⊙ 문제 풀이

 

import sys

input = sys.stdin.readline

N = int(input())
L = list(map(int, input().split()))
J = list(map(int, input().split()))
L, J = [0] + L, [0] + J
dp = [[0 for _ in range(101)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, 101):
        if L[i] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]] + J[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][99])

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!