[백준/Python] 14501 : 퇴사

 

 

남아있는 일 수와 이익끼리의 조합 중 조건에 맞는 조합쌍을 찾고, 그 중에서 이익 합계가 최대가 되도록 하는 쌍을 선택하는 브루트포스 알고리즘 문제이다.

 

N = int(input())
T = [0] * N
P = [0] * N
for i in range(N):
    T[i], P[i] = map(int, input().split())

# 퇴사 이후까지 기간이 넘어가는 것들부터 삭제
for i in range(N-1, -1, -1):
    if (N-i < T[i]) :
        T.pop(i)
        P.pop(i)

arr = [0]*(N+1)
max_val = 0

for i in range(len(T)-1, -1, -1):
    time = T[i] + i
    arr[i] = max(max_val, P[i] + arr[time])
    max_val = arr[i]

print(max_val)

 

T와 P를 각각 N개의 원소를 가진 리스트로 생성하여 순서대로 입력받았고,

그 다음에 퇴사 이후까지 기간이 넘어가는 일정을 삭제하기 위해 마지막 일정부터 역으로 거슬러 올라가면서 기간이 초과되는 일정의 T와 P 원소를 pop 해주었다.

이렇게 상담이 가능한 일정들에 대해서만 정제되었다면, max 값을 저장할 arr 배열과 max_val 변수를 생성한다.

이에 대해 for문을 끝에서부터 역순으로 진행하면서 0으로 채워진 arr 배열의 i 번째 값을 max_val 과 P[i]+arr[time] 값 중 큰 값을 저장하도록 하였다.

 

이렇게 마지막으로 계산 완료된 max_val을 출력하면 얻을 수 있는 최대 이익이 나올 것이라고 생각했는데,

몇몇 예제에서는 숫자가 -1 된 상태로 출력되어 다음과 같이 오류가 발생하는 것을 알 수 있었다....

 

 

런타임 에러는 for문 내에서 i를 잘못된 위치에 작성했던 문제였고, 이를 수정해도 코드 자체가 틀렸다고 나왔다.

따라서 다음은 수정 완료한 최종 정답 코드이다.

 

 

---

 

 

<최종 코드>

N = int(input())
T = [0] * N
P = [0] * N
for i in range(N):
    T[i], P[i] = map(int, input().split())

arr = [0] * (N + 1)

for i in range(N - 1, -1, -1):
    time = i + T[i]
    if time <= N:  # 기간이 넘어가지 않는 경우에만 계산
        arr[i] = max(arr[i + 1], P[i] + arr[time])
    else:
        arr[i] = arr[i + 1]

print(arr[0])

 

 

앞선 코드에서 따로 먼저 기간 초과 요소를 삭제할 때 pop() 을 통해 정제했던 부분이 아마 pop()을 사용한 것으로 인해 인덱스가 엉켜서 오답일 수도 있을 것 같았다.

따라서 해당 for문 전체를 없애고, 그냥 max 값을 구하는 for문 내에 if문( if time <= N )으로 넣어서 코드를 더 요약했음

미리 정제 작업을 안거치니까 아래 for문에서도 len(T)가 아닌 N-1 부터 역순으로 시작하면 되었다.

 

max 값을 정하는 부분도 아예 max_val 변수를 없애고, arr[i] = max(arr[i+1], P[i] + arr[time]) 으로 수정하여

arr[i+1]은 현재 상담을 하지 않고 다음 날로 넘어갔을 때 얻을 수 있는 최대 이익, 

P[i] + arr[time] 은 현재 상담을 했을 때의 금액 + 상담 종료 후 얻을 수 있는 최대 이익 

둘 중에 큰 값을 선택하도록 수정하였다.

 

상담이 전체 일수를 초과하는 경우, 현재 상담을 할 수 없으므로 arr[i] = arr[i+1],

즉 단순히 다음 날의 최대 이익을 그대로 가져온다.

 

마지막으로 arr[0], 즉 첫째 날부터 상담을 시작했을 때 얻을 수 있는 최대 이익을 출력한다.