[백준,PS,재귀,DP,삼성SW][PYTHON] #14501. 퇴사

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

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

[정 리]

 

1. 조합을 이용해서 구해보자

 

   1.1 - 일수가 지나서 이용할 수 있는 스케쥴이라면 1 그렇지 않다면 0의 조합으로 나타내보자.

 

   1.2 - 7일동안의 스케쥴을 생각해본다면 0000000 부터 1111111 까지의 조합으로 이루어 질것이다.

 

   1.3 - 이들의 조합중 제한사항으로 인해 걸리는 것을 제외하여 (ex: 1000100) 해당idx의 P[i]값들을 더하여 최댓값을 구한다.

 

def getResult(x):
    global _max
    if x ==N:
        day_count = 0
        total =0
        for i in range(x):
            if(result[i] ==1 and day_count ==0):
                day_count = T[i]
                total += P[i]
            if day_count >0:
                day_count = day_count -1
        if day_count ==0:
            _max = max(total,_max)
            
            
            
    else:
        for i in range(2):
            result[x] = i 
            getResult(x+1)
        
N = int(input())#리스트의 전체의 길이
T = [0] *N #시간 input받을 리스트
P = [0]* N#수익 input 받을 리스트
result = [0] *N
_max = -1
for i in range(N):
    T[i], P[i] = map(int, input().split())

getResult(0)
print(_max)

 

[다른풀이]

 

1. DP