[백준] 14501번 퇴사 파이썬(Python) 풀이🚩

14501번: 퇴사

 

[문제]

---

[코드]

n = int(input())
day = []
money = []

dp = [0]  * (n + 1)
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    day.append(x)
    money.append(y)

for i in range(n-1, -1, -1):
    time = day[i] + i
    if time <=n:
        dp[i] = max(money[i] + dp[time], max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value

print(max_value)

---

[해설]

 

 

 이 풀이의 핵심은 '다이나밍 프로그래밍'  (동적 계획법)이다. [줄여서 'DP'] 

사실 나도 전공자가 아니기 때문에 이러한 용어에 익숙하지 않지만 이번 문제를 풀면서 좀 더 자세히 살펴볼 수 있었다. [이는 코드 해설이후 자세히 기록해 두었다.]

 

1. 우선 총 날짜를 input()으로 받고 이를 변수로 지정한다

그리고 day와 money의 빈 리스트를 생성한다.

n = int(input())
day = []
money = []

 

2. 그리고 dp를 생성하는데 n+1번째 날이 퇴사를 하는 기쁜 날이기 때문에 n+1길이 만큼 생성한며

max_value값을 생성하여 0으로 지정한다 (max_value 값은 우리가 원하는 출력값으로 그날에 최대로 땡길 수 있는 금액을 의미한다)

dp = [0]  * (n + 1)
max_value = 0

 

3. 그리고 for 문을 활용해서 x=걸리는 날, y=받는 금액을 input()으로 받고 이를 각각 day리스트와 money리스트에 추가한다

for _ in range(n):
    x, y = map(int, input().split())
    day.append(x)
    money.append(y)

 

4. 다음이 이 문제의 핵심 풀이라고 할 수 있는데 우선 for문을 활용해서 위에서 아래로 내려오게한다(역순)

그런다음 time이라는 변수를 지정하고 이는 i번째 걸리는 날 + i를 더한 값으로 이 값이 n보다 작을때만 계산이 작동하게 한다. 만약 크다면 이는 그날의 상담을 할 수 없기 때문에 그냥 넘어가게한다.

 

먼저 0으로 채워진 dp의 i번째 값을 money[i] + dp[time(=day[i] + i)]와 max_value중 큰값을 저장하고

d이를 다시 max_value로 지정한다.

 

그리고 이러한 계산이 끝나고 난 후 max_value를 출력하면 우리가 원하는 값이 출력된다.

for i in range(n-1, -1, -1):
    time = day[i] + i
    if time <=n:
        dp[i] = max(money[i] + dp[time], max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value

print(max_value)

 

 > 코드가 돌아가면 어떻게 계산이 될까?

예제 1의 값을 입력했을 때 돌아가는 원리 

<예제1 입력>

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

---------------------------------------- else
i: 6
time 8
dp: [0, 0, 0, 0, 0, 0, 0, 0]
max_value: 0
---------------------------------------- else
i: 5
time 9
dp: [0, 0, 0, 0, 0, 0, 0, 0]
max_value: 0
---------------------------------------- if time <=n
i: 4
time 6
dp: [0, 0, 0, 0, 15, 0, 0, 0]
max_value: 15
---------------------------------------- if time <=n
i: 3
time 4
dp: [0, 0, 0, 35, 15, 0, 0, 0]
max_value: 35
---------------------------------------- if time <=n
i: 2
time 3
dp: [0, 0, 45, 35, 15, 0, 0, 0]
max_value: 45
---------------------------------------- if time <=n
i: 1
time 6
dp: [0, 45, 45, 35, 15, 0, 0, 0]
max_value: 45
---------------------------------------- if time <=n
i: 0
time 3
dp: [45, 45, 45, 35, 15, 0, 0, 0]
max_value: 45

---

다이나믹 프로그래밍 Dynamic programming, Dp

최적화 이론의 한 기술이며, 트정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

즉, 이전의 값을 활용해서 답을 구하는 것이다 (쉽게 설명하면)

이는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.

 

 

그렇다면 DP는 왜 사용할까?

일반적인 재귀방식 또한 DP와 비슷한 부분이 많이 존재하지만 재귀방식의 경우 동일한 작은 문제해결 방식이 반복해서 사용되기 때문에(같은 방법이 계속 반복) 비효율적이라는 것이다.

이는 파보나치 수열의 문제를 예로 들 수 있다.

위 사진은 파보나치 수열을 재귀함수를 사용했을때의 트리 모양이다.

f함수의 계산을 계속해서 사용하고 있다는 것을 확인할 수 있다. 이는 숫자가 커지면 계산의 횟수가 기하 급수적으로 증가한다.

그러나 위의 계산값들을 자세히 보면 중복되는 계산결과가 많다는 것을 확인할 수 있다.

즉 이를 dp에 저장해서 불러온다면 계산의 횟수를 효율적으로 줄일 수 있다.

 

더 자세한 설명은 아래 블로그를 참조 

알고리즘 - Dynamic Programming(동적 계획법)