[코드트리 삼성기출] 외주 수익 최대화하기

📌문제 출처

코드트리 삼성 SW 역량테스트 기출문제
https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

📗 풀이 코드

input = open(0).readline

def solution(n,t_p):
    dp = [0]*(n+1) # (n+1) dp 생성, i번째 업무까지 확인했을 때 얻을 수 있는 최대 수익
    sta,end,income = [0],[0],[0] # index를 맞추기 위해 0추가
    for i in range(n):
        sta.append(i+1) # 시작일
        end.append(i+t_p[i][0]) # 종료일
        income.append(t_p[i][1]) # 수익
    # i번째 업무까지 확인했을 때 일자별로 얻을 수 있는 최대 수익 확인
    for i in range(1,n+1) : # 업무 하나씩 확인
        if n < end[i] : # 종료일이 휴가 기간보다 늦으면 업무 진행 못하므로 확인할 필요 없음
            continue
        for j in range(0,i): # i번째 업무는 i일에 시작하기 때문에 i일 이전에 시작하는 업무들 확인
            if end[j] < sta[i] : # i번째 업무를 할 수 있으려면 이전 시작한 업무들이 i일 이전에 끝나야함
                dp[i] = max(dp[i], dp[j]+income[i]) # 업무 진행 X와 업무 진행비교
    return max(dp)

if __name__ == '__main__' :
    n = int(input())
    t_p = [list(map(int, input().split())) for _ in range(n)]
    print(solution(n,t_p))

 

💯 풀이 설명

• 마지막으로 i번째 업무를 진행했을때 최대로 얻는 수익을 dp[i]에 담아줄 것이다.
• 일자와 인덱스를 맞춰주기 위해 dp와 업무별 시작일, 종료일, 수익에 모두 0을 담아두고 시작한다.
• dp는 최대 수익이기에 모두 0으로 넣어준다.
• for문으로 모든 업무를 하나씩 확인한다. 우선 i번째 업무의 종료일이 휴가 기간보다 늦으면 업무를 하지 못하므로
  확인할 필요가 없다.(0으로 고정)
• j번째 업무(첫번째부터 i-1번째 업무까지) 확인하면서 i번째 업무를 진행할 수 있으려면 j번째의 업무가 이미 종료되어있어야 한다. 이에 조건문을 넣어준다
• dp[i]는 j for 문이 도는 동안 계속 갱신된다.
  이에 따라 j번째 업무까지 확인했을 때 최대 수익 +  i번째 업무를 진행했을 때 최대 수익 중 최대값이 된다.
• 최종적으로 dp에서 최대값을 반환한다.