[DFS] 백준#14501: 퇴사/Python

📝 문제

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

14501번: 퇴사

💡 접근법

DFS 알고리즘으로 문제를 해결하였습니다. 다이나믹 프로그래밍(DP)로도 문제 해결이 가능합니다. DP 관련 풀이는 이곳을 참고해 주시고, 본 포스팅에서는 DFS 기반 풀이만 공유합니다. 문제 풀이의 핵심은 상담 수수료는 낮은데 상담 소요일이 긴 근무일은 근무를 하지 않도록 하는 것입니다. 예를 들어, 근무 가능일이 \(4\)일 남았고 상담 수수료와 소요일이 아래 표와 같이 주어졌다고 가정해 보겠습니다. 

근무일	Day 1	Day 2	Day 3	Day 4
상담 수수료	20	30	40	50
상담 소요일	2	3	4	5

 

결론부터 말씀드리자면, Day 1과 Day 2 중 하루만 근무할 수 있는 상황이며, Day 2에 근무해야 문제를 풀 수 있습니다. Day 1에 근무를 하게 되면 2일이 소요되어 Day 3부터 상담을 재개할 수 있습니다. 하지만, Day 3과 Day 4는 상담 소요일이 근무가 가능한 일보다 높기 때문에 추가 근무가 불가능합니다. 반면, Day 2에 근무를 하면 Day 4에 상담이 종료되고 추가 근무는 불가하지만 상담 수수료는 Day 1에 근무하는 것보다 큰 \(30\)을 얻습니다. 이처럼, 근무 가능일과 얻을 수 있는 이익을 고려하여 특정 날은 일부러 근무하지 않는 로직이 필요합니다. 이어지는 섹션에서 이를 고려하여 작성한 코드를 공유해 드립니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

def consult(day, p_total):
    global answer
    # 퇴사일의 경우
    if day == N:
        answer = max(answer, p_total) # 최대이익으로 정산
        return
    t = Work[day][0] # 상담 소요일
    p = Work[day][1] # 상담 수입

    # 해당 일부터 상담하는 경우
    if t + day <= N:
        consult(t + day, p_total + p)
    # 해당 일의 다음 날부터 상담하는 경우
    consult(day + 1, p_total)

if __name__ == "__main__":
    N = int(input())
    Work = [list(map(int, input().split())) for _ in range(N)]
    answer = 0
    # 시작일 순차적으로 방문
    for day in range(N):
        consult(day, 0)
    print(answer)

2) 해설

(1) 데이터 입력 속도 개선

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

(2) DFS 알고리즘

def consult(day, p_total):
    global answer
    # 퇴사일의 경우
    if day == N:
        answer = max(answer, p_total) # 최대이익으로 정산
        return
    t = Work[day][0] # 상담 소요일
    p = Work[day][1] # 상담 수입

    # 해당 일부터 상담하는 경우
    if t + day <= N:
        consult(t + day, p_total + p)
    # 해당 일의 다음 날부터 상담하는 경우
    consult(day + 1, p_total)

DFS 알고리즘을 활용하여 특정 날(day)에 바로 상담을 시작하는 경우와 해당 일의 다음 날(day+1)부터 상담을 시작하는 경우로 나누어 퇴사일까지 얻을 수 있는 이익을 모두 계산합니다. 퇴사일이 되면, 모든 경우의 수로부터 얻는 상담 수수료의 최댓값을 정답(answer)으로 선정합니다.

(3) 메인함수

if __name__ == "__main__":
    N = int(input())
    Work = [list(map(int, input().split())) for _ in range(N)]
    answer = 0
    # 시작일 순차적으로 방문
    for day in range(N):
        consult(day, 0)
    print(answer)

✅ 채점 결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14501.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

해당 문제를 다이나믹 프로그래밍(DP)로도 문제를 해결해 봤습니다. DP 관련 풀이는 이곳을 참고해 주세요.

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.