완전탐색 | BOJ 백준 14501번 퇴사 | Python


created_at : 27 March 2024 - 3 mins read time
Tags: 완전탐색 DP 동적프로그래밍

Table of Contents


BOJ 백준 14501번 퇴사 | Python

📌 백준 14501번 문제 바로가기

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

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

🔎 문제 설명

🩶 실버 3

- 난이도 ★★☆☆
- 완전탐색 & 동적프로그래밍

전형적인 완전탐색 문제. 이 문제는 2가지 풀이법이 있다.

  1. 완전탐색
    • 걸리는 시간과 비용을 모두 고려해야 하기 때문에 T 와 P 를 넘겨주면서 재귀로 풀 수 있다.
    • 상담하지 않고 지나간다면 T+1 와 P 그대로 반환.
    •  
  2. 동적 프로그래밍 (DP)
    • for문을 2개 돌려서 그때그때의 최대가 되는 값을 계산
    • N 값이 커진다면 시간 복잡도 고려해야 함



💻 내 코드

1. 완전탐색

N = int(input())
reserv = []
for _ in range(N):
    # t: 기간 / p: 받을 수 있는 금액
    t, p = map(int, input().split())
    reserv.append((t,p))
    
result = [0 for _ in range(N+1)]
answer = 0

def search(time, price):
    global answer
    answer = max(answer, price)
    if time >= N: return
    if time + reserv[time][0] <= N:
        search(time + reserv[time][0], price + reserv[time][1])
    search(time + 1, price)
    return

search(0,0)
print(answer)

2. 동적 프로그래밍 (DP)

N = int(input())
reserv = []
for _ in range(N):
    # t: 기간 / p: 받을 수 있는 금액
    t, p = map(int, input().split())
    reserv.append((t,p))

result = [0 for _ in range(N+1)]

## DP 동적프로그래밍
for i in range(N):
    for j in range(i+reserv[i][0], N+1):
        if result[j] < result[i] + reserv[i][1]:
            result[j] = result[i] + reserv[i][1]
            
print(result[-1])




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).