728x90
*문제 출처는 삼성전자, 코드트리에 있습니다.
삼멘 1일차
문제 제목: 외주 수익 최대화하기
나의 풀이
문제 봤을때 '하 이거 많이 봤는데 뭐였더라' 했음
코테를 장기간 풀지 않았어서 까먹었고...
생각해내다가 메모이제이션이지! 했다.
근데 처음에 너무 이상한 메모이제이션을 해버림..
일단 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
다른 풀이 - 백트래킹(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)
728x90
'coding test - python > SAMSUNG SWT(SW역량 테스트)' 카테고리의 다른 글
삼성 SW역량테스트 기출 / 2017 하반기 오후 2번 문제 연산자 배치하기 - DFS / Python 파이썬 (0) | 2024.09.14 |
---|---|
삼성 SW역량테스트 기출 / 2017 하반기 오전 1번 문제 조삼모사 - 조합, 백트래킹 / Python 파이썬 (1) | 2024.09.14 |
삼성 SW역량테스트 기출 / 2015 하반기 1번 문제 바이러스검사 - Greedy / Python 파이썬 (0) | 2024.09.13 |
[삼성 SW 역량테스트 대비] 삼성 역량테스트 준비하기 (3) | 2024.09.12 |
[삼성 SW 역량테스트 대비] 빈출 개념 6가지 (배열 회문, 조합, 순열 등) (4) | 2024.09.12 |