[실버 2] 백준 1535 - 안녕 (파이썬)

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

풀이

친구들에게 인사를 할 수 있는데, 각 친구에게 인사를 하면 체력이 감소하고, 기쁨은 증가한다.

체력이 100 이하가 되면 죽기 때문에, 체력을 1 이상 유지하면서 얻을 수 있는 최대 기쁨의 합을 구하는 문제이다.

모든 친구들에게 인사할 수 있는 경우의 수는 2^N이다.

브루트포스로 가능한 모든 친구 조합을 만들고, 그 조합이 체력 조건을 만족하는지 확인 후 기쁨은 계산하면 풀 수 있다.

max_jsum = 0
for i in range(0, N + 1) :
    for combination in combinations(range(N), i) :
        lsum = 0
        jsum = 0

        for j in combination :
            lsum += L[j]
            jsum += J[j]
        
        if lsum < 100 :
            max_jsum = max(max_jsum, jsum)

combinations(range(N), i)를 통해서 친구들 중 i명을 선택한 조합을 생성한다.

조합 내 친구들에게 인사를 했을때 총 체력 소모 lsum이 100 미만이면, 가능한 선택이기 때문에 jsum과 비교해서 최대값을 갱신한다.

코드

# 백준 1535 - 안녕
# 분류 : 브루트포스

from itertools import combinations

N = int(input())
L = list(map(int, input().split()))
J = list(map(int, input().split()))

max_jsum = 0
for i in range(0, N + 1) :
    for combination in combinations(range(N), i) :
        lsum = 0
        jsum = 0

        for j in combination :
            lsum += L[j]
            jsum += J[j]
        
        if lsum < 100 :
            max_jsum = max(max_jsum, jsum)

print(max_jsum)