1535 - 해결

안녕

 

문제

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 

이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.

 

세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 

세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 

세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

 

세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다.

 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 

 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N(<=20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 

잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 

얻는 기쁨이 1번 사람부터 순서대로 들어온다. 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

---

combonation 으로 인덱스를 구하고 그거에 따라 최대 행복을 구하고 저장하는 방식을 사용하기로 했다.

시간 초과 걸릴 줄 알았는데 다행히 바로 통과하였다.

 

import sys

N = int(sys.stdin.readline())

# 체력, 행복 리스트
heal_list = list(map(int,sys.stdin.readline().split()))
hap_list = list(map(int,sys.stdin.readline().split()))

from itertools import combinations

# 인덱스를 구하기위한 리스트
n_list = [i for i in range(N)]

# 최대 행복
max_hap = 0

# 어차피 다구하는 거라 반대로 해도 상관 없음
for i in range(N,0,-1):
    # 인덱스 콤비 구하기
    combi = list(combinations(n_list,i))
    
    # 인덱스 해보기
    for idxs in combi:
        total_heal = 0
        total_hap = 0
        # 인덱스로 체력, 행복 구하기
        for idx in idxs:
            total_heal += heal_list[idx]
            total_hap += hap_list[idx]
            # 밖에 하나만 있어도 되지만 뭔가 빨리 돌리기 위해서 안에도
            if total_heal >= 100:
                break
        if total_heal >= 100:
                continue
        # max 행복
        if max_hap < total_hap:
            max_hap = total_hap

print(max_hap)