[백준/알고리즘/python/java] 1535번 - 안녕

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

 일단, 나도 처음에 틀렸던 문제다. 그리디 문제로 접근을 했었고, 문제를 풀었는데, '예제 입력 5' 와 같은 반례에 부딪혔다. 

나의 로직은 이러했다. 

문제에서 1번 사람부터 N번 사람까지 순서대로 잃는 체력리스트와 얻는 기쁨 리스트를 입력받는다.

세준이가 얻을 수 있는 최대 기쁨을 출력하는 것이므로,

[hp(체력), joy(기쁨)]을 쌍으로 갖는 새로운 리스트를 만든 후에, joy(기쁨)을 기준으로 내림차순 정렬을 한다.

그러면, 큰 joy(기쁨)를 가지는 쌍이 앞에 오겠고 해당하는 hp(체력)을 초기 HP(100)에서 빼가면서 음수나 0이 아니면,

해당 joy(기쁨)을 그대로 더해주면서 for문을 순회하도록 로직을 짰다.

 

처음에 짠 로직은 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())
HP = 100
joy = 0

# 1번 사람부터 N번 사람까지의 잃는 체력 리스트
lose_hp = list(map(int,input().split()))
# 1번 사람부터 N번 사람까지의 얻는 기쁨 리스트
get_joy = list(map(int,input().split()))

# [lose_hp와 get_hoy 쌍]을 새로운 리스트에 저장
trade_off_set = []
for i in range(N):
    trade_off_set.append([lose_hp[i],get_joy[i]])
print(trade_off_set)

# get_joy기준으로 내림차순 정렬하고 , 
# 초기 HP(100)에서 각 joy에 해당하는 hp를 빼면서
# 양수면 joy를 더해주는 방식으로 순회한다.
looking_for_optimal = sorted(trade_off_set, key = lambda x : x[1],reverse=True)  
print(looking_for_optimal)
answer = 0 
for x in looking_for_optimal:
    if HP - x[0] > 0:   # x[0]은 [hp,joy]쌍에서 hp를 뜻한다. 이것이 양수면
        HP -= x[0]  # 기존 HP에서 빼주면서 저장
        answer += x[1]  # 기존 answer에도 해당 joy(x[1])를 더해준다.
print(answer)

여기서, 다른 예제는 다 맞았지만, '예제 입력 5' 와 같은 반례는 해결해주지 못했다. 나의 로직에 따르면 '예제 입력 5'는

아래와 같은 리스트를 도출해준다.

# 예제 5번 입력
8
100 26 13 17 24 33 100 99
34 56 21 1 24 34 100 99

# 새로운 리스트
[[100, 100], [99, 99], [26, 56], [100, 34], [33, 34], [24, 24], [13, 21], [17, 1]]
# 가 된다.

여기서 얻을 수 있는 기쁨의 최댓값은 99가 되는데, 답은 135이다.

[100,100]은 지나쳐도 [99,99]를 만날 때, 100-99 = 1 로 HP가 바뀌어서 그 이후에는 고려하지 않기 때문이다. 

 

즉, 나중은 생각하지 않고, 지금 그 순간만을 고려하는 그리디로 풀어서 이런 결과를 만든 셈이다.

여기서, 가장 최적의 기쁨을 도출하는 경우는 [hp, joy] 기준으로 [26, 56], [33, 34], [24, 24], [13, 21] 이다.

 

hp 는 100 - 26 - 33 - 24 - 13 = 4 가 되고 joy 는 56 + 34 + 24 + 21 = 135 가 나오는 경우다.

 

즉, 이 문제는 그리디가 아니라 다이나믹 프로그래밍으로 풀어야 한다. 구글링을 통해 이 문제는

대표적인 배낭 알고리즘이라는 것을 알게 되었다.

 

이참에 배낭 알고리즘에 대해 배워보자.

배낭 알고리즘에 대해서 잘 설명해 높은 블로그가 있어서 해당 블로그를 참고하면 될 것 같다.

배낭정리의 기본 개념은,

• i 번째 물건을 배낭에 넣을 수 없다.
  -> i-1 개의 물건들을 갖고 구한 전 단계의 값을 그대로 가져온다.
• i 번째 물건을 배낭에 넣을 수 있다.
  -> max(i-1 개의 물건들을 갖고 구한 전 단계의 값, i 번째 물건만큼의 무게를 비웠을 때의 값 + i 번째 물건)

이다.

핵심은

이전 최대가치와 이전 값을 빼고

현재 값을 넣은 것과 비교하여 더 가치가 높은 것을 넣어주는 것이다.

코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())

# 1번 사람부터 N번 사람까지의 잃는 체력 리스트
lose_hp = list(map(int,input().split()))
# 1번 사람부터 N번 사람까지의 얻는 기쁨 리스트
get_joy = list(map(int,input().split()))

lose_hp = [0] + lose_hp 
get_joy = [0] + get_joy

# 체력 0부터 100까지 N 명의 사람 
dp = [[0 for _ in range(101)] for _ in range(N+1)]


#8
#0 100 26 13 17 24 33 100 99 - hp
#0 34 56 21 1 24 34 100 99 - joy

for i in range(1,N+1):  # 사람 수 
    for j in range(1,101):  # 체력을 늘려가면서 들어갈 수 있는지
        if j - lose_hp[i] > 0 : # 들어갈 수 있을 때
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-lose_hp[i]] + get_joy[i]) 
        else: 
            dp[i][j] = dp[i-1][j]

print(dp[N][99])

예제 1번 입력에 대한 dp를 찍어보면 아래와 같다.

[
[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, 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, 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, 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, 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, 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, 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, 0, 0, 0, 0, 0, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 24, 24, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 24, 24, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 80, 80, 80, 80, 80, 80, 80, 80, 80, 90, 90, 90, 90, 101, 101, 101, 101, 101, 101, 101, 101, 101, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 135, 135, 135, 135],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 24, 24, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 80, 80, 80, 80, 80, 80, 80, 80, 80, 90, 90, 90, 90, 101, 101, 101, 101, 101, 101, 101, 101, 101, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 135, 135, 135, 135],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 24, 24, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 80, 80, 80, 80, 80, 80, 80, 80, 80, 90, 90, 90, 90, 101, 101, 101, 101, 101, 101, 101, 101, 101, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 135, 135, 135, 135]
]