[boj] 안녕_1535

www.acmicpc.net/problem/1535

1535번: 안녕

최대 이득을 얻기 위해 주어진 보기들을 적절하게 골라내야 하는 문제다.

문제를 보자마자 DP의 향기가 진하게 뿜어져 나왔지만 사실 어떻게 접근해야 하는지는 잘 몰랐다.

 

그래서 백트래킹을 이용한 재귀함수 호출로 문제를 해결하려고 시도했더니 엥? 풀렸다...

나중에 알고보니 이 문제는 '냅색(knapsack)' 문제로, 다이나믹 프로그래밍의 아주 대표적인 유형이라더라. 그래서 DP로 다시풀었다.

 

이 문제를 풀기 전에 '평범한 배낭_12865' 문제로 유형을 익히니 사실상 코드에서 변수명만 바꿔주는 수준으로 풀리더라는...

문제를 푸는 자세한 방법은 위 포스팅에 있다.

 

이 문제가 하나 다른점이 있다면, 평범한 배낭 문제는 시간제한 때문에 백트래킹을 이용한 재귀는 사용할 수 없다는 점이었다.

 

+) 문제에서 총 체력이 100이고 체력이 0이하로 떨어지면 안된다는 조건이 있었는데, 나는 냅색 문제로 더 가까이 접근해 풀기 위해서 0부터 체력을 시작해 사람을 만날수록 체력이 쌓여 99가 최대인 조건으로 바꾸어 풀었다. 마치 체력 99가 냅색의 최대 용량인 것처럼 말이다.

 

• 재귀함수 + 백트래킹을 이용한 코드 (체력을 쌓아가는 식이 아닌 깎아주는 식으로 풀었다.)

"""
백트래킹 재귀를 이용한 풀이
"""
n = int(input())

costs = list(map(int, input().split()))
joys = list(map(int, input().split()))

life = 100
result = 0

# 현재 인덱스, 현재 기쁨, 현재 라이프를 인자로 연산하는 재귀함수
def Recursion(idx, cur_joy, cur_life):
    global result

    # 종료조건 : 라이프가 0이하일 때
    if cur_life <= 0:
        # 이전의 기쁨을 결과로 리턴
        prev_joy = cur_joy-joys[idx-1]
        if prev_joy > result:
            result = prev_joy
        return

    # 종료조건 : 모든 사람을 탐색했을 경우
    if idx == n:
        if cur_joy > result:
            result = cur_joy
        return

    # 현재 사람을 선택할 경우
    Recursion(idx+1, cur_joy+joys[idx], cur_life-costs[idx])
    # 현재 사람을 선택하지 않을 경우
    Recursion(idx+1, cur_joy, cur_life)

Recursion(0, 0, life)
print(result)

 

• 2차원 다이나믹 프로그래밍을 이용한 풀이 (체력을 깎아가는 방식이 아닌 0에서 채우는 방식으로 풀었다.)

"""
2차원 DP를 이용한 풀이
"""

n = int(input())

costs = [0]
joys = [0]

cost = list(map(int, input().split()))
joy = list(map(int, input().split()))

costs += cost
joys += joy

costs_limit = 99

dp = [[0] * 100 for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(100):
        if costs[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-costs[i]] + joys[i], dp[i-1][j])

print(dp[n][costs_limit])