[삼성SW역량][Python/BOJ] 백준 14501 퇴사(DFS)

 

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

14501번: 퇴사

 

코드 : 

 

 

def dfs(idx, val) :
    if idx == n+1 :
        global answer
        answer = max(answer,val)
        return 
    else :
        if idx + T[idx] <= n+1 :
            dfs(idx+T[idx], val+P[idx])
        dfs(idx+1, val)

n = int(input())
T = [0]# 인덱스를 날짜로 사용하고 싶어서(1부터 사용하고 싶어서)
P = [0]
answer = 0

for i in range(n) :
    a,b = map(int,input().split())
    T.append(a)
    P.append(b)

dfs(1,0)
print(answer)

 

 

인덱스를 날짜로 사용하고 싶어서 0으로 둘다 채워넣었습니다.

1일차부터 불러냅니다. 

 

 

만약 일 할 날짜를 넘으면 answer 를 저장한 후 return 합니다.

 

 

그렇지 않으면 

일을 했을 때와 안했을 때로 나뉩니다.

오늘 일을 해도 n+1보다 작다면 일을 하는 경우와

일은 안하고 날짜만 가는 경우로 나뉩니다. 

 

---

 

 

내가 생각한 코드 : 

n = int(input())
T,P = [],[]
answer = 0
for i in range(n) :
    a,b = map(int,input().split())
    T.append(a)
    P.append(b)
    
def dfs(idx,val) :
    if idx > n :
        return 
    if idx == n :
        global answer
        answer = max(answer,val)
        return 
    dfs(idx+T[idx],val+P[idx])
    dfs(idx+1,val)
    
dfs(0,0)
print(answer )

0 안넣고 그냥 할 수 도 있습니다.

 

 

 

---

 

 

 

좀 더 간단한 코드 : 

 

def dfs(day,pay) :
    global ans 
    if day > n : return 
    if day == (n) :
        ans = max(ans,pay)
        return 
    else :
        # 오늘 (day)의 상담을 안한다.
        dfs(day+1, pay)
        # 오늘 (day)의 상담을 한다. 
        dfs(day+arr[day][0],pay + arr[day][1])


if __name__=="__main__" :
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    ans = 0
    
    dfs(0,0)
    print(ans)

 

오늘 날짜에 상담을 하느냐 안하느냐의 경우를 모두 돌아보도록 DFS를 만들었습니다. 

 

 

 

코드 출처 : 

 

인프런 - 김태원 파이썬 강의 

 

복습 : 

✅ 20220701

✅ 20220914