완전탐색(유형정리) - 백준 14501

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

3	5	1	1	2	4	2
10	20	10	20	15	40	200

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이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

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

예제 입력 1 복사

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1 복사

45

 

개인적으로 이게 왜 실버3인지 이해가 안 되었던 문제이다. 단순하게 문제 자체를 이해하는 것은 매우 쉽다. 그냥 7일을 입력하면 7개의 칸에 각 날짜마다 끝낼 수 있는 시간과 이익이 기록된다. 여기서 가장 큰 이익을 낼 수 있는 경우의 이익값을 구해주면 된다. 문제 이해는 엄청 쉬운데, 구현을 하다 재귀를 떠올리기까지 너무 오랜 시간이 걸렸던 문제였다.

 

def Max_profit(day, profit):
    global sum
    
    if day > N+1:
        return
    if day == N+1:
        sum = max(sum, profit)
        return
    Max_profit(day+T[day], profit+P[day])
    Max_profit(day+1, profit)
    
N = int(input())


T = [0]*(N+1)
P = [0]*(N+1)

for i in range(1,N+1):
    T[i], P[i] = map(int, input().split())
    
sum = 0

Max_profit(1,0)
print(sum)

 

나는 문제를 이렇게 해결했다.

 

1. 총 N+1개 칸의 T,P 리스트를 만들고 각각을 N개 만큼 입력받는다.

2. 함수 내에서 전역변수로 sum 변수를 만들어준다.

3. day가 N+1 이라면 일을 할 수 있는 경우이므로 이 때 max 이익을 계산해주고 스톱

4. day가 N+!을 넘어설 경우 일을 할 수 없는 경우이므로 바로 스톱

5. 재귀로 일을 하는 경우 day에 T 리스트 값을 더해주고, 이익에는 P 리스트 값을 더해준다.

6. 재귀로 일을 못하는 경우 그냥 day를 하루 늘려주고, 이익은 그대로 둔다.

7. 1일 부터 시작하므로 함수를 (1,0)으로 호출시켜주고 max값이 된 전역변수 sum을 출력시킨다.

 

이 알고리즘을 그대로 따라가면서 일을 하는 경우, 일을 못하는 경우를 나누어 생각해주었다.

 

재귀도 생각하기 힘든 문제였지만, global변수로 sum을 선언해주지 않으니 애초에 sum 변수 컨트롤이 힘들어서 함수 내 변수선언법을 구글링해보았고, 이를 통해 전역변수 선언방식 중 함수 내에서 global 변수로 선언하는 방식도 있다는 것을 알게 되었다.

 

문제를 모두 풀고 나서 다른 사람들의 풀이가 궁금하여 구글링을 해보았더니, 브루트포스로 푼 사람들은 나와 비슷하게 재귀함수를 사용하였고, 대다수 dfs와 dp를 사용하였다. dp 알고리즘을 아직 모르는 상태라 추가적인 공부가 필요할 듯 하다.