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

문제

카운셀러로 일하고 있는 현수는 오늘부터 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

 

풀이

아 딱 보고 dfs로 걍 풀면 되겠는데? 했다가 몇시간 날림. 나의 경험과 스킬을 탓하자...

max = 0

def dfs(L, sum):
    global max
    if L == n+1:
        if sum > max:
            max = sum
        return

    if L + days[L] <= n+1:
        dfs(L+days[L], sum+pays[L])
    dfs(L+1, sum)


n = int(input())
days = list()
pays = list()
for i in range(n):
    a, b = map(int, input().split())
    days.append(a)
    pays.append(b)
    
#날짜가 1일부터 시작하니까 index=0에다가 0을 넣어줘서 index랑 날짜랑 맞춰줌...이러면 쉬운걸...
days.insert(0,0)
pays.insert(0,0)

dfs(1, 0)
print(max)

 

내가 시간을 5시간정도 날렸는데, 그 이유는 딱 한가지다. 문제를 잘못 읽어서..

문제에선 분명히 N+1일째에 휴가를 가야 된다고 했다. 이 말은 N일전에 상담을 시작해도, 끝나는 날이 N일을 초과한다면 그 일은 시작할 수 없다는 것이다...

따라서 dfs함수에서 dfs로 들어가기 직전 if문에서

 L + days[L] <= n+1

로 걸러줘야 했다. 

그리고, 끝나는 날짜도, n+1을 초과하는 날짜가 아니라, 딱 n+1이 되는 그 날짜에 멈춰줘야 한다. 어차피 각각의 날짜에 상담을 안하면 dfs(N+1, sum)으로 하루하루씩 날짜가 증가하기 때문에 n+1에 걸리게 되어있다.

 

나중에 다시 해보잣.