삼성 SW역량테스트 기출 / 2017 상반기 오전 2번 문제 외주 수익 최대화하기 - DP / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 1일차

문제 제목: 외주 수익 최대화하기

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit?&utm_source=clipboard&utm_medium=text

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

 

 

---

나의 풀이

 

문제 봤을때 '하 이거 많이 봤는데 뭐였더라' 했음

 

코테를 장기간 풀지 않았어서 까먹었고...

 

생각해내다가 메모이제이션이지! 했다.

 

근데 처음에 너무 이상한 메모이제이션을 해버림..

 

일단 dp를 역순으로 하는 이유는

 

 

• 우리는 i번째 날을 선택할지 말지를 결정하는 상황
• 만약 i번째 날에  선택하면, 해당 업무가 끝나는 날 이후의 최대 수익을 고려해야 함. 이때 해당 업무가 끝나는 날은 i + arr[i][0]가 됨 (현재 인덱스 + 걸리는 날)
• 반면, 선택하지 않는다면 그 다음 날인 i+1번째 날의 최대 수익을 고려하게됨

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(n+1)]
arr = [list(map(int, input().split())) for _ in range(n)]

for i in range(n-1, -1, -1):
    if i + arr[i][0] <= n:
        dp[i] = max(dp[i+arr[i][0]] + arr[i][1], dp[i+1])
    else:
        dp[i] = dp[i+1]

print(dp[0])

 

• dp[i + arr[i][0]] + arr[i][1]: i번째 날에 상담을 선택했을 때 얻는 수익.
• dp[i + 1]: i번째 날에 상담을 하지 않고 얻는 수익.
• max(...): 두 경우 중 더 큰 값을 선택하여 i번째 날의 최적 수익을 결정.

 

 

비슷한 유형 참고
https://sillon-coding.tistory.com/461

백준 / 퇴사 - 다이나믹 프로그래밍 (bottom-up) / Python 파이썬

 

 

 

 

다른 풀이 - 백트래킹(Backtracking)

- 모든 가짓 수에 대해 탐색

n = int(input())

given_time_profits = [
    tuple(map(int, input().split()))
    for _ in range(n)
]

times = [
    (i, i + time - 1)
    for i, (time, _) in 
    enumerate(given_time_profits, start = 1)
]

profits = [
    profit 
    for _, profit in given_time_profits
]

selected_jobs = []
max_profit = 0


# 선택한 외주 작업에 대한 수익을 반환해줍니다.
def get_profit():
    return sum([
        profits[job_idx]
        for job_idx in selected_jobs
    ])


# 수행하고자 하는 외주 작업들이 수행 가능한지 여부를 확인합니다.
def is_available():
    # 이전 외주의 종료일이 그 다음 외주의 시작 보다 늦은 경우 이는 불가능한 경우입니다.
    for i in range(len(selected_jobs) - 1):
        _, end_time = times[selected_jobs[i]]
        start_time, _ = times[selected_jobs[i + 1]]
        if end_time >= start_time:
            return False
    
    # 각 외주의 종료일이 휴가 기간을 초과하는 경우 이는 불가능한 경우입니다.
    for job_idx in selected_jobs:
        _, end_time = times[job_idx]
        if end_time > n:
            return False
    
    return True


def find_max_profit(curr_idx):
    global max_profit
    
    # 모든 외주 작업에 대해 다 탐색한 경우 스케쥴링이 가능한지를 확인한 뒤
    # 가능한 최대 수익을 갱신해줍니다.
    if curr_idx == n:
        if is_available():
            max_profit = max(max_profit, get_profit())
        return
    
    # 해당 인덱스의 외주 작업을 수행하지 않았을 때의 경우를 탐색합니다.
    find_max_profit(curr_idx + 1)
    
    # 해당 인덱스의 외주 작업을 수행했을 때의 경우를 탐색합니다.
    selected_jobs.append(curr_idx)
    find_max_profit(curr_idx + 1)
    selected_jobs.pop()


find_max_profit(0)
print(max_profit)

---