[Algorithm] 삼성 SW 역량테스트 2017 상반기 오전 2번 문제 외주 수익 최대화하기, 코드트리 | 파이썬 (DP, Dynamic Programming)
※ 외주 수익 최대화하기
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
[문제]
일의 휴가 동안 외주 개발을 하여 수익을 최대화 하려고 합니다. 수행할 수 있는 외주 작업이 하루에 한 개씩 있고, 각 외주 작업은 수행 완료하는데 걸리는 기한 와 이를 완료 했을 때의 수익 가 주어집니다. 두 개 이상의 외주 작업은 동시에 수행할 수 없으며, 휴가 기간 이후로는 일을 할 수 없다고 할 때 외주 수익의 최대값을 출력하는 코드를 작성해보세요.
예를 들어 이고 외주 작업이 다음과 같이 주어진 경우를 생각해봅시다.
번 외주를 같이 하게 된다면 일해야하는 기간이 겹치게 되어 불가능합니다.
번 외주를 같이 하게 된다면 겹치지 않게 일을 할 수 있고, 총 만큼의 돈을 얻게 됩니다.
번 외주만 하게 된다면 만큼의 돈을 얻게 됩니다.
[입력 조건]
첫 번째 줄에는 이 주어지고,
두 번째 줄부터 번째 줄까지는 각 일자에 수행할 수 있는 외주 작업의 기한 와 수익 가 공백을 사이에 두고 주어집니다.
[출력 조건]
가능한 외주 수익의 최대값을 출력합니다.
[입력 예시1]
2
2 5
1 4
[출력 예시1]
5
[입력 예시2]
3
2 5
2 7
1 3
[출력 예시2]
8
[입력 예시3]
3
2 10
2 26
1 15
[출력 예시3]
26
문제 해결 TIP
예제 2번을 예시로 들면, 다음과 같이 5 + 3 = 8인 경우가 최대이다.
첫째줄부터 하루씩 밀려서 계산해야 함으로 i+t로 dp에 넣어준다. 외주 작업 일수를 계산하기 전 항상 업데이트를 해주고, 만약 일을 할 수 있는 날이라면 최대값으로 dp에 넣어준다.
전체 코드
n = int(input())
work = []
for i in range(n):
work.append(list(map(int,input().split())))
dp = [0]*(n+1)
day =0
for i in range(n):
t, p = work[i]
dp[i] = max(dp[i], dp[i - 1])
if i + t <= n:
dp[i+t] = max(dp[i+t],dp[i] + p)
print(max(dp))