[백준] 삼성 SW 역량 테스트 기출 문제 14501번 : 퇴사 (파이썬/Python)

[백준] 삼성 SW 역량 테스트 기출 문제 14501번 : 퇴사 (파이썬/Python)

문제 링크

정답 전체 코드

N = int(input())
T = []
P = []
    
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
    
DP = [0] * (N+1)
    
for i in range(1, N+1):
    for j in range(1, i+1):
        if j + T[j-1] - 1 <= i:
            DP[i] = max(DP[i], DP[j-1] + P[j-1])
    
result = max(DP)

print(result)

설명

문제 설명

이 문제는 백준이가 퇴사하기 전에 할 수 있는 상담의 최대 이익을 구하는 문제이다.
남은 N 일 동안 상담을 통해서 최대한 많은 수익을 얻고 싶어한다. 각 상담을 완료하는 데 걸리는 기간(Ti)과 상담을 했을 때 받을 수 있는 금액(Pi)로 이루어져 있다. 이 문제의 목표는 상담 일정을 잘 조정하여 백준이가 얻을 수 있는 금액을 최대로 하는 금액을 구하는 것이다.

문제 접근 방법

이 문제를 해결할려면 복잡한 문제를 여러 개의 부분 문제로 나누어 해결한 뒤 그 결과를 저장해두었다가 나중에 부분 문제를 합쳐서 복잡한 문제를 해결하는 방식인 "다이나믹 프로그래밍" 기법을 사용하여 해결한다.

알고리즘 설명

1. 입력 받기 : 먼저 N, T, P 를 입력 받는다. 각각은 상담 가능한 날짜 수, 각 상담을 완료하는 데 걸리는 기간, 상담을 완료했을 때 받을 수 있는 금액을 의미한다.
2. DP 배열을 초기화한다. N+1 크기의 DP 배열을 초기화한다. 이 배열의 각 요소는 해당 일까지 얻을 수 있는 최대 수익을 저장한다.
3. DP 를 이용하여 최대 수익을 계산한다.

• 외부 루프에서는 1일부터 시작하여 N 일까지 순회한다.
• 내부 루프에서는 현재 날짜(i) 와 상담을 시작할 수 있는 날짜(j)를 비교한다.
• 상담을 시작할 수 있는 날짜(j)는 상담 기간(T[j-1])을 고려하여 현재 날짜(i) 이전이어한다.
• 조건을 만족하는 경우, DP 배열을 업데이트합니다. 즉, DP[i] 는 현재 저장된 값과 DP[j-i] + P[j-i] 중 더 큰 값으로 업데이트한다.

4. 결과를 출력한다. 결과는 DP 배열에서 가장 큰 값을 찾으면 된다.

코드 설명

1. N, T, P를 입력받아 초기화
2. DP = [0] * (N+1)을 통해 DP 배열을 초기화한다. 이 배열은 각 일자까지 얻을 수 있는 최대 수익을 저장한다.
3. 이중 for 루프를 사용하여 모든 가능한 상담 조합을 해보는 것이다. 내부 루프에서 j + T[j-1] - 1 <= i 조건을 통해 상담을 완료할 수 있는지 확인을 하고 진행한다. 가능하다면, DP[i]를 현재 값과 DP[j-1] + P[j-1] 중 더 큰 값으로 업데이트한다.
   4, 마지막으로 max(DP)를 통해 DP 배열에서 가장 큰 값을 찾아 출력한다. 이 값이 최대 수익이다.