BOJ) 안녕

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

1535번: 안녕

 

이 문제 또한 어제 풀었던 냅색 알고리즘 문제이다.

 

import sys
input = sys.stdin.readline


n = int(input())
arr = [0]+list(map(int, input().split()))

happy = [0] + list(map(int, input().split()))


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

for i in range(1, n+1):
    for j in range(1, 101):
        hap = happy[i]
        hp = arr[i]

        if hp > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], hap + dp[i-1][j-hp])

print(dp[n][99])

 

솔직히 문제를 끝까지 읽지않아 dp[n][100]를 출력했더니 모두 오답이었고, dp[n]을 출력한 결과 99번째가 정답임을 발견하여 dp[n][99]로 정정하여 무난하게 풀 수 있었다. (dp[n][100]은 hp가 100일때, 즉 사망하여 기쁨이 0이 된다는 뜻이다.)

 

다른 사람의 풀이를 보고자 검색하였고 알고리즘 분류에 브루트 포스가 있음에도 모두 냅색 알고리즘을 이용해 풀은 풀이들이었다.

때문에 브루트포스로 한 번 풀어보았다.

 

import sys
from itertools import combinations
input = sys.stdin.readline


n = int(input())
hp = list(map(int, input().split()))

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

dic = {}

answer = 0

for i in range(n):
    dic[hp[i]] = joy[i]

for idx in range(1, n+1):
    for arr in combinations(hp, idx):
        left_hp = 100
        max_joy = 0
        for i in range(len(arr)):
            i_hp = arr[i]
            i_joy = dic[arr[i]]

            if i_hp >= left_hp:
                answer = max(answer, max_joy)
                break
            else:
                max_joy += i_joy
                left_hp -= i_hp
                answer = max(answer, max_joy)

print(answer)

 

우선 combination을 이용해 1부터 n+1까지 combination의 배열 갯수를 선택했다. (permutation은 중복된 배열이 존재하게 되므로 사용하지 않았다.)

 

그리고 매 배열(combination으로 생성한 배열)마다 hp 100와 max_joy 0값을 주어 남은 hp가 현재 깎일 hp보다 많거나 같다면 반복문을 탈출, answer값을 갱신해준다.

 

---

냅색 알고리즘은 한 번 이해를 하면 어느정도 까지는 쉽게 풀 수 있는 문제같다.

그러나 dp문제들의 난이도가 워낙 하늘과 땅차이라 잊어버리는 것을 둘째치고 골드 상위구간부터는 어떻게 풀어야할까 고민이다.