문제 : 퇴사
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
문제 정리
- 모든 경우의 수를 탐색하는 문제인 Brute force문제이다.
- 배낭 문제(Knapsack Problem)의 한 변형으로 보인다.
- 여기서 '시간'이 배낭 문제에서의 '무게 제한'이고
- 상담의 '이익'이 배낭 문제에서의 '가치'에 해당
- 즉, 동적 프로그래밍이나 재귀적 접근으로 접근해야한다. - 주어진 조건에 맞게 각 날짜에 해당하는 상담을 하는 것과 안하는 것으로 나뉜다.
문제 풀이
# 입력
n = int(intput()) # 남은 근무일
consulting = [list(map(int,input().split())) for _ in range(n)] # 상담 종류
def consulting_plan(consulting, n, idx, total_p):
# 종료조건 설정 : 퇴사일이 넘어간다면 된다면 종료(1이 아니라 0부터 시작하기에 등호가 필요)
if idx>=n:
return total_p
# 현재 날짜의 상담이 가능한가? 즉, 상담을 시작하면 퇴사일이 넘어가지 않는가?
if consulting[idx][0]+idx <= n:
p_with_consulting = consulting_plan(consulting, n, consulting[idx][0]+idx, total_p+consulting[idx][1])
# 현재 날짜의 상담이 어렵다면 상담 종료
else:
p_with_consulting = total_p
# 현재 날짜의 상담을 pass하고 다음 날짜의 상담을 고려
p_without_consulting = (consulting, n, idx+1, total_p)
# 가장 이득이 되는 총 상담비 출력
return max(p_with_consulting, p_without_consulting)
print(onsulting_plan(consulting, n, 0, 0)) # 최종 상담 출력조건 : 상담종료일이 퇴사일을 넘으면 안된다.
한 날짜에서 경우의 수는 두가지(현재 날짜를 상담, 현재 날짜를 상담하지 않음)이다.
조건과 경우의 수에 맞게 재귀를 실행시키면 된다.
주어진 조건이 얼마 없어 실버3인 듯 하다.
나름 난이도가 적절했다. 재귀라는 것 자체가 접근하기 힘든 문제이기에 나름 고전을 했지만..ㅠ
