https://www.acmicpc.net/problem/14501
sol) 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램 ⇒ 상담할 수 있는 모든 경우의 수를 구해 최대수익 결과 return
1. 첫째줄에 n , 둘째 줄부터 상담을 완료하는데 걸리는 기간(T)과 상담을 했을 때 받을 수 있는 금액(P) 받아오기
n = int(input())
profit = [list(map(int,input().split())) for _ in range(n)]
2. 상담을 하는 경우와 안하는 경우 모든 경우의 수 계산 (재귀 사용)
- 만일 2일에 잡혀있는 상담이 총 t만큼 걸린다고 하면 다음 상담은 t+2일부터 가능하다
def recur(idx, p) :
#해당 일에 상담을 하는 경우
recur(idx + profit[idx][0] , p + profit[idx][1])
#해당 일에 상담을 하지 않을 경우
recur(idx + 1 , p )
3. 예외적용하기
- 만일 7일에 잡혀있는 상담이 2일이 걸리는 상담이라면 퇴사일을 넘어서므로 상담을 할 수 없다
- 즉, 상담이 잡혀 있는 날 + 상담을 하는데 걸리는 기간(idx)이 퇴사일(n)을 넘어서면 안된다
def recur(idx, p ) :
global answer
if idx >= n :
#만일 퇴사일을 넘어설 경우 결과 X
if idx > n :
return
#최대 수익일 경우 업데이트
answer = max(answer , p)
return answer
#해당 일에 상담을 하는 경우
recur(idx + profit[idx][0] , p + profit[idx][1])
#해당 일에 상담을 하지 않을 경우
recur(idx + 1 , p )
4. 전체코드 작성
def recur(idx, p ) :
global answer
if idx >= n :
#만일 퇴사일을 넘어설 경우 결과 X
if idx > n :
return
#최대 수익일 경우 업데이트
answer = max(answer , p)
return answer
#해당 일에 상담을 하는 경우
recur(idx + profit[idx][0] , p + profit[idx][1])
#해당 일에 상담을 하지 않을 경우
recur(idx + 1 , p )
n = int(input())
profit = [list(map(int,input().split())) for _ in range(n)]
answer = 0
recur(0,0)
print(answer)
탑다운 DP 방식
n = int(input())
interview = [list(map(int,input().split())) for _ in range(n)]
#계산된 결과를 저장하기 위해 dp 초기화
dp = [-1 for _ in range(n)]
def recur(idx) :
if idx == n-1 : #마지막 일자에 끝나면 0반환
return 0
if idx > n :
return -99999
#상담을 하는 경우 와 안하는 경우 중 더 많은 돈을 버는 경우를
#dp 테이블에 저장하겠다 (큰 값을 dp[idx]로 저장)
dp[idx] = max(recur(idx + interview[idx][0]) + interview[idx][1], recur(idx+1) )
return dp[idx]
recur(0)
print(dp)
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[백준] 2606번 바이러스 - 파이썬 (2) | 2023.10.05 |
---|---|
다이나믹 프로그래밍 - 파이썬 (1) | 2023.10.05 |
[백준] 2961번 도영이가 만든 맛있는 음식 - 파이썬 (1) | 2023.10.04 |
[백준] 2503번 숫자야구 - 파이썬 (0) | 2023.10.03 |
기초 알고리즘 [정렬] (0) | 2023.09.27 |