본문 바로가기
알고리즘/백준

[백준 14501] 퇴사 (C++)

by Bloofer 2020. 6. 16.

A. 문제설명

https://www.acmicpc.net/problem/14501

문제에 대한 자세한 설명은 링크 참조

 

1. 퇴사전 남은 N일동안 최대한 많은 상담을 하려함

2. 상담시 걸리는 시간 Ti와 받는 보수 Pi가 각각 일별로 주어짐

3. 상담일의 일정을 적절히 배분하여 보수를 최대로 받을 수 있는 금액 구하기

 

B. 접근법

DFS + 시뮬레이션

 

N일의 일정동안 상담을 수행할지 말지에 대한 시리얼로 조합을 구하고 해당 조합을 완전탐색으로 시뮬레이션 한다. 그 중 최대가 되는 보수를 구하기

 

C. 풀이

1. 모든 조합을 만듬 2^15개 최대

2. for 모든 조합에 대한 시뮬레이션 수행, 그러나 불가능하면(일정 겹치거나, 안끝나는 것) 중간 종료

3. 매 시뮬레이션이 끝날 때, 수행 값의 최대를 업데이트

 

D. 내 코드