[BOJ_Python] 1535. 안녕

문제

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

 

사용 알고리즘

0/1 Knapsack

 

풀이

고려사항

1. 현재 부분 집합 기준에 인사 가능한 체력이 있는지

2. 인사 가능하다면, 인사 할지에 대한 여부 확

 

후기

1. 이 문제는 조건의 N이 20 이하이며, 체력은 100 미만이라는 작은 범위로 인해

Brute Force, 백트레킹, 0/1 Knapsack 모두 사용이 가능하다.

하지만, 가장 효율적인 방법으로 0/1 Knapsack을 적용하여 풀었다.

Brute Force : $ O(2^{N}) $

Knapsack : $ O(100 * N) $

 

2. 이후, 코드느 기본 Knapsack 코드와 동일하다.

 

코드

import sys
input = sys.stdin.readline

# 총인원
N = int(input())
# 사용되는 체력, 얻는 기쁨 관련 리스트
hp = [0] + list(map(int, input().split()))
joy = [0] + list(map(int, input().split()))

# knapsack 정보 업데이트
knapsack = [[0] * (100) for _ in range(N + 1)]
for i in range(1, N + 1):  # 만나는 사람
    for j in range(1, 100):  # 사용된 체력

        # 현재 만나는 사람만 인사했을 때에도 체력이 부족한 경우
        if j < hp[i]:
            knapsack[i][j] = knapsack[i - 1][j]
        # 현재 만나는 사람과 인사가 가능한 경우
        else:
            # 인사를 하는 경우, 하지 않는 경우 비교
            knapsack[i][j] = max(knapsack[i - 1][j], joy[i] + knapsack[i - 1][j - hp[i]])

print(knapsack[N][99])

 

결과