휴가(삼성 SW역량평가 기출문제 : DFS활용)
카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.
현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.
만약 N = 7이고, 아래와 같이 예약이 잡혔있다면
1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.
하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.
휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이며, 이때의 이익은 20+30+10=60이다.
현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)
▣ 출력설명
첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.
▣ 입력예제 1
7
4 20
2 10
3 15
3 20
2 30
2 20
1 10
▣ 출력예제 1
60
import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)
# 상담 완료 걸리는 날 T, 상담 했을 때 받는 금액 P
n = int(input())
data = []
for _ in range(n):
T, P = map(int, input().split()) #날, 금액
data.append((T,P))
data.insert(0,(0,0)) #1~n까지 하기 위해/
res = 0
def DFS(L, sum):
global res
if L == n+1: #종료조건. 다 확인했으니
if sum > res:
res = sum
else: #여기서 생각해야 하는 것은 걸리는 날짜!
#조건을 하나 더 추가했어야 했어
#L이 오늘 날짜고 +data[L][0] 했을 때 이게 n을 넘어가면 더하면 안되잖아 !! 이거 고려해줬어야 한다 !!!
if L + data[L][0] <=n+1: #n+1날이 되면 종료조건이니까.
DFS(L+data[L][0], sum + data[L][1])
DFS(L+1, sum) #오늘 안하고 다음 날로 이동.
DFS(1,0) #1일부터 시작.
print(res)코멘트
이 문제 역시 부분 집합 유형의 DFS문제.
현재 노드를 선택할지 말지를 선택하는 것이지. (부분집합 유형으로 풀면 돼)
근데 이 문제의 중요한 점은 +1씩 가는게 아니였어 !!! 해당 날짜를 해결한 기간을 더해주는거라 그 기간 즉 L + data[L][0]이 종료조건 n+1을 넘어가는 순간 그건 더할 수 없잖아. 이 조건이 꼭 필요했다 !!!
-
거기에 더해서 해당 날짜를 사용안하는건 L+data[L][0]과는 관계가 없으므로 if문 안에서 실행하면 안되고 밖에서 실행하면 돼.
-
핵심은 같은데 조건 하나 떄문에 헷갈림.. 생각 잘 하자 !
