BOJ(백준) 14501[퇴사]

안녕하세요! 오늘은 백준의 14501번 문제인 “퇴사” 문제를 함께 풀어보겠습니다. 이 문제는 도영이가 퇴사하기 전까지 최대한 많은 수익을 얻기 위해 상담 일정을 조정하는 문제입니다. 함께 문제를 해결해보도록 하죠!

1. 문제 설명

1) 도영이는 퇴사를 하고 난 후, N일 동안 상담을 하며 수익을 얻으려 합니다.

2) 각 상담은 상담을 완료하는 데 걸리는 기간과 상담을 통해 얻을 수 있는 수익이 주어집니다.

3) 도영이는 퇴사하기 전까지 최대한 많은 수익을 얻고자 합니다.

4) 도영이가 퇴사하는 날까지 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하세요.

 

문제 URL: https://www.acmicpc.net/problem/14501

2. 접근법

1) 입력받기: 상담 기간과 수익 정보를 입력받습니다.

2) 재귀 함수 정의: 모든 상담 일정을 고려하여 최대 수익을 재귀적으로 계산합니다.

3) 결과 출력: 가능한 최대 수익을 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력받는 부분
# 전체 상담 기간 (N일)
N = int(input())
# 각 일자별 상담 기간과 수익
sd = [list(map(int, input().split())) for _ in range(N)]  

ans = -1  # 최대 수익을 저장할 변수, 초기값은 -1로 설정

# 재귀함수 정의
def rec(day, price):
    global ans      # 전역변수 ans를 사용하기 위해 선언
    if day < N:     # 현재 날짜가 전체 기간보다 작을 때
        ans = max(price, ans)  # 현재 수익과 기존 최대 수익을 비교하여 더 큰 값을 ans에 저장
    elif day == N:    # 현재 날짜가 전체 기간과 같을 때
        ans = max(price, ans)  # 현재 수익과 기존 최대 수익을 비교하여 더 큰 값을 ans에 저장
        return      # 함수 종료
    elif day > N:     # 현재 날짜가 전체 기간을 초과할 때
        return      # 함수 종료
    # 현재 상담을 선택하는 경우
    rec(day + sd[day][0], price + sd[day][1])  # 상담을 진행한 후 날짜와 수익을 갱신하여 재귀 호출
    # 현재 상담을 선택하지 않는 경우
    rec(day + 1, price)  # 다음 날로 넘어가서 재귀 호출

rec(0, 0)  # 재귀함수 최초 호출, 첫날부터 시작하며 초기 수익은 0

print(ans)  # 최대 수익 출력

 

4. 코드 설명

1) 입력받는 부분

• N을 입력받아 전체 상담 기간을 설정합니다.

• 각 일자별 상담 기간과 수익을 입력받아 sd 리스트에 저장합니다.

2) 전역 변수 초기화

• ans 변수를 초기화하여 최대 수익을 저장할 준비를 합니다.

3) 재귀 함수 정의

• rec 함수는 day와 price를 인자로 받아 호출됩니다.

• 함수는 다음 세 가지 조건에 따라 동작합니다:

1. day < N: 현재 날짜가 전체 기간보다 작을 때, 현재 수익과 기존 최대 수익을 비교하여 더 큰 값을 ans에 저장합니다.

2. day == N: 현재 날짜가 전체 기간과 같을 때, 현재 수익과 기존 최대 수익을 비교하여 더 큰 값을 ans에 저장하고 함수를 종료합니다.

3. day > N: 현재 날짜가 전체 기간을 초과할 때, 함수를 종료합니다.

• 재귀 호출:

• 현재 상담을 선택하는 경우, 상담 기간을 더한 다음 날 day와 상담 수익을 더한 price로 재귀 호출합니다.

• 현재 상담을 선택하지 않는 경우, 다음 날로 넘어가서 재귀 호출합니다.

4) 재귀 함수 초기 호출

• rec(0, 0)으로 재귀 함수를 처음 호출하여 첫날부터 시작하며 초기 수익은 0으로 설정합니다.

5) 결과 출력

• print(ans)를 통해 최대 수익을 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_05_03_14501.py at main · pcy4196/coTest