[알고리즘] 휴가(삼성 SW역량평가 기출문제 : DFS활용)

휴가(삼성 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)

출력설명

첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.

테스트케이스

입력예제	출력예제
7 4 20 2 10 3 15 3 20 2 30 2 20 1 10	60
5 3 10 2 15 1 10 1 30 2 10	45
7 3 40 2 15 3 50 3 25 2 20 2 30 1 10	80

---

해결방법

상담을 했다 안 했다 방식으로 접근하면 된다.

1. 상담 시간을 저장하는 T 리스트와 상담을 통해 얻을 수 있는 P 리스트를 생성한다.
2. 각각 T리스트와 P 리스트에 첫번째 인덱스에 0의 값을 삽입한다. 이유는 날짜를 인덱스 0 기준이 아닌 1 기준으로 접근하려고 한다.
3. 현재 날짜 + 현재 날짜의 삼담 시간은 N+1 이상의 값을 넘으면 안된다.
4. DFS함수의 매개변수는 L과 sum으로 L은 현재 날짜 그리고 sum은 더한 돈이다.
5. 현재 날짜가 N+1이 됐을 경우, sum의 값을 res와 비교하여 최신화 시킨다.
6. 상담을 했을 경우 다음 L은 L+T[L]이 된다. 왜냐하면 다음 상담일은 오늘 상담일 L 더하기 오늘 상담을 하면 기다려야하는 상담시간 T[L] 이기 때문이다.
7. 상담을 했을 때 sum의 매개변수는 P[L] + sum으로 상담을 했기 때문에 값을 더한다.
8. 만약 상담을 하지 않았을 경우 L은 그냥 L+1이 되며 sum 값으로는 그대로 있는다.

---

코드

# 날짜, 
def DFS(L, sum):
    global res
    # n + 1 일 때, 끝낸다
    if L == n+1:
        if sum > res:
            res = sum
    else:
        # L 번째 상담을 한다고 가정 했을 경우
        # L : 날짜, T[L] : 해당 날짜에 걸리ㅣ는 시간
        # L + T[L] => 다음을 볼 날짜
        if L + T[L] <= n + 1:
            # 상담을 했을 때 상황
            DFS(L+T[L], sum + P[L])
        # 상담을 하지 않았을 경우
        DFS(L+1, sum)


n = int(input())

# 걸리는 시간
T = list()
# 얻을 수 있는 금액
P = list()

for i in range(n):
    a, b = map(int, input().split())
    # 걸리는 시간
    T.append(a)
    # 얻을 수 있는 금액
    P.append(b)

res = -2147000000

# insert를 한 이유는 날짜를 index 0으로 안보고 1부터 보기 위해서 0을 칸 채우는 것이다.
T.insert(0, 0)
P.insert(0, 0)

# 날짜 돈
DFS(1, 0)

print(res)