[백준] 14501 퇴사 - 파이썬(dp말고 다른 풀이)

우선 저는 python 쟁이라 python 풀이입니다:>

• 문제링크: https://www.acmicpc.net/problem/14501 

14501번: 퇴사

• 난이도: 실버 3
• 유형: dp or backtracking

해당 문제를 풀다가 잘 모르겠어서 풀이를 찾아보니까 보통 dp로 풀어서 다른 방법 없다 생각하다가 해당 문제가 N =15 임을 보고 그냥 다 계산하는 방법을 생각했습니다! 전체 날짜에 대해서 모두 o/x를 한다고 해도 2^15이라 (2^10=1024는 10^3과 비슷하므로 10^9 보단 훨씬 작기에 가능합니다:)) 백트레킹방법으로 하였는데 풀이는 아래와 같습니다. 

 

• 파이썬 풀이

#back tracking (2**N = 2**15 < (10**3)**2 r가능!)
import sys
#sys. setrecursionlimit(10000)
# input
n = int(sys.stdin.readline())
sch = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# back tracking
def dfs(nn, tempans):
    # nn: 며칠인지
    # tempans: temp ans
    global ans #def 밖에 있는 것과 연동
    if nn >= n:
        ans=max(tempans, ans) # 다른 길로 갔을 때의 값과 비교해서 큰 것
        return
    # 상담 실행 o - 퇴사전까지만 가능
    if nn+sch[nn][0]<=n:
        dfs(nn+sch[nn][0], tempans+sch[nn][1])
    # 상담 실행 X
    dfs(nn+1, tempans)
    
ans= 0
dfs(0,0)

print(ans)