📁백준 14501 퇴사 -Python

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

✅실버 III

14501번: 퇴사

 

📌문제

🖋 예제입력 1             🖋 예제출력 1              🖋 예제입력 2              🖋 예제출력 2

7                                  45                                    10                                 55
3 10                                                                     1 1
5 20                                                                     1 2
1 10                                                                     1 3
1 20                                                                     1 4
2 15                                                                     1 5
4 40                                                                     1 6
2 200                                                                   1 7

                                                                            1 8

                                                                            1 9

                                                                            1 10

 

🖋 예제입력 3             🖋 예제출력 3              🖋 예제입력 4              🖋 예제출력 4

10                                     20                               10                                 90     
5 10                                                                      5 50
5 9                                                                        4 40
5 8                                                                        3 30
5 7                                                                        2 20
5 6                                                                        1 10
5 10                                                                      1 10
5 9                                                                         2 20
5 8                                                                         3 30
5 7                                                                         4 40
5 6                                                                         5 50

 

 

💻 수정 전 코드

import sys

N = int(sys.stdin.readline()) #일하는 날짜 입력

List = []

check = 0

for i in range(N):

    List.append(list(map(int, sys.stdin.readline().split())))

Work = len(List)

Rwork=[]

NMoney = 0

T_Profit=[] # 전체 이익

for i in range(Work):

    if (Work - i) < List[i][0] :  # 근무일수 > 남아있는 근무일수

        List[i][0] = 0  # 필요한 근무수 = 0

        List[i][1] = 0  # pay = 0

    elif (Work -i) == List[i][0]:

        check = i

for i in range(Work): # 가능한 일 수만큼 반복

    NDate = i  # 일 한 일수

    while(True):    

        if NDate == Work:  # 전체 일수와 가능한 일수가 같을 경우

            break

        elif List[NDate][0] == 0:

            break

        else:

            Rwork.append(NDate)  # 진짜 일할 수 있는 날짜를 카운트

            NDate += List[NDate][0]

    if List[check-1][1] < List[check][1] and i < check:  #현재 일하는 것보다 그 뒤에가 더 클 경우

                Rwork.pop()

                Rwork.append(check)

    j = 0

    for j in range(len(Rwork)):

        NMoney += List[Rwork[j]][1]

    T_Profit.append(NMoney)

    Rwork.clear()

    NMoney = 0

print(max(T_Profit))

 

 

예제의 결과값은 다 나왔지만 틀렸다.

 if List[check-1][1] < List[check][1] and i < check:  #현재 일하는 것보다 그 뒤에가 더 클 경우

아마도 이 부분에서 에러가 나는 것 같다.

 

💻 수정 후 코드

 

 

N = int(input())  # 일하는 날짜 입력

work = [list(map(int, input().split())) for _ in range(N)]  # 상담 정보 입력 (소요 시간, 금액)

# dp[i]: i일까지 얻을 수 있는 최대 수익

dp = [0] * (N + 1)  # N일 동안 얻을 수 있는 최대 수익을 저장할 리스트, N+1로 설정하는 이유는 마지막 날까지 계산을 용이하게 하기 위함

for i in range(N):

    time, pay = work[i]  # 현재 상담을 완료하는데 필요한 시간과 받을 수 있는 금액

    if i + time <= N:  # 해당 상담을 할 수 있는 경우

        dp[i + time] = max(dp[i + time], dp[i] + pay)  # 상담을 완료하는 날짜에 대한 최대 수익을 업데이트

    dp[i + 1] = max(dp[i + 1], dp[i])  # 다음 날짜에 대한 최대 수익을 현재까지의 최대 수익과 비교하여 업데이트

print(dp[N])  # N일까지 얻을 수 있는 최대 수익 출력

 

 

 

 

📖 참고 

◾ Dynamic Programming( DP, 동적 계획법)

복잡한 문제를 여러개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결하는 방법

ex) 피보나치 수열
▪ 사용조건

- 최적 부분 구조(Optimal Substructure)

- 겹치는 부분 문제(Overlapping Subproblems)

▪ 적용 방식

- Top - Down → 재귀함수 이용하여 구현

- Bottom - Up → 반복문을 이용하여 구현

 

◾ Memoization (저장)

- 동일 계산 반복 시 이전 계산값을 메모리에 저장하여 실행속도를 빠르게 함

→ 불필요한 연산을 줄여줌!!

 

🎈알고리즘 분류

- 다이나믹  프로그래밍

- 브루트포스 알고리즘