[백준/14501/파이썬] 퇴사

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

14501번: 퇴사

Problem

• 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
• 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

조건

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

SOL

우선, N이 매우 작은 문제이다. 

항상 어떤 문제든지, 완전탐색(브루트포스)로 풀 수 있는지 없는지 판단을 먼저하는게 좋다. 왜냐하면, 완전탐색으로 풀 수 있다면, 그 문제는 어떻게든 풀 수 있다는 거니까, 딱 봤을때, 완전탐색으로 ~~~게 풀 수 있겠다 싶으면, 그걸로 푸는게 맞다고 생각함. ( DP,backtracking 등은 그 뒤의 문제이다)

 

완전탐색의 가능성

1번째 일 선택한 상태 -> 그 상태에서 2번째 상태, 3번째 상태 등을 선택하는,모든 경우를 탐색한다고 생각해보자.

우선, 완전탐색을 한다고 하면, 모든 경우의 수를 생각해보자. max(nC1,nC2,nC3,nC4....nCn) 일 거다.

일반적으로 nCr 인 조합의 수의 O(2^n)이다. (itertools combinations는 찾아보니까, 그것보단 훨 -씬 빠르다고한다) .

물론, 문제의 경우에도, 조건에 맞는 상담일만 가능하므로, 2^n 보다는 훨씬 작은 경우의 수를 가지게 될거다.

2^n이라고 해도, 2^15 정도면, 충분히 가능한 범위다.

그래서, 조건에 맞게 dfs를 해주는 , backtracking으로 구현도 가능할거 같음.

 

DFS+backtracking

• if day>=tc: 상담하는 일보다, day가 크거면, 상담을 진행할 수 없다. 그리고, day(퇴사하는 날) 함수를 종료한다. 
• 그리고, 문제의 조건을 보면, T[i] =3 이면, 해당 당일 + 다음날 +이틑날 이렇게 3일동안 불가능한거임. 이와 같이, 생각을 해주면, day+board[day][0]==tc라도, 상담이 가능하다. 
• 따라서, 부등호를 잘 생각해줘야함. 단, day가 tc가 되었으면, 그 이상의 상담을 못하기 때문에, 그만 해야한다.

#DFS+backtracking

tc = int(input())
#board[day][0] = T[i] , board[day][1]= P[i]
board= [list(map(int,input().split())) for _ in range(tc)]
answer = -1

def dfs(day,payment):
    global answer
    answer = max(answer,payment)
    if day>=tc:
        return
    if day+board[day][0]<=tc:
        dfs(day+board[day][0],payment+board[day][1]) #상담이 가능해서,하는경우 
    dfs(day+1,payment) #상담을 하지 않고, 넘어가는게 더 클수도 있기 때문에, 상담을 하지않는 경우
    return

dfs(0,0)
print(answer)