[Algo Rhythm🕺💃]BOJ 14501 - 퇴사

문제분석

백준이는 $i (1 \le i \le N)$번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 단순히 생각하면 i번째 날의 일을 하는 경우와 안 하는 경우로 나눠서 모든 경우를 살핀 뒤 그 중 최대의 이익을 구하면 될 것 같다. 사실 그래도 된다. 하지만 조금 더 생각해보면 보다 더 효율적인 방법이 있다는 것을 알 수 있다.

 

앞서 말했듯이 백준이는 i번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 자세히 말하면 만약 i번째 날의 일을 한다면 $i + T[i]$번째 날의 일부터 하느냐 마느냐를 선택할 수 있고 만약 i번째 날의 일을 하지 않는다면 $i + 1$번째 날의 일부터 하느냐 마느냐를 선택할 수 있다. 즉, 백준이가 i번째 날의 일을 하느냐 마느냐를 결정할 수 있는 상황에서 얻을 수 있는 최대 이익은 i번째 날의 일을 선택했을때 얻을 수 있는 최대 이익과 i번째 날의 일을 선택하지 않았을 때 얻을 수 있는 최대 이익 중 더 큰 값이다.

 

우리는 이를 통해 문제 해결에 연쇄적인 구조가 있음을 알 수 있고 이는 전형적인 dynamic programming의 해결방법임을 파악할 수 있다.

 

문제 풀이

문제 분석에서 언급한 '백준이가 i번째 날의 일을 하느냐 마느냐를 결정할 수 있는 상황에서 얻을 수 있는 최대 이익은 i번째 날의 일을 선택했을때 얻을 수 있는 최대 이익과 i번째 날의 일을 선택하지 않았을 때 얻을 수 있는 최대 이익 중 더 큰 값'은 아래와 같은 점화식으로 표현할 수 있고 $f(i)$의 값을 memoization table에 저장하고 필요할 때 불러서 사용할 수 있다.

 

$f(i) = max\begin{cases}f(T[i] + i) + P[i]&if\ choose\ i^{th}\ day\\f(i+1)&if\ not\ choose\ i^{th}\ day\end{cases}​$

 

점화식을 재귀함수로 구현하고나서 따로 처리해야 하는 두 가지 예외상황들이 있다. 하나는 i 번째 날이 백준이가 퇴사하는 N + 1번째 날보다 크거나 같은 상황이고 다른 하나는 $T[i] + i - 1$ 일 즉, 백준이가 i번째 날의 일을 하고나서 다음으로 일을 할 수 있는 날이 N+1 일보다 크거나 같은 상황이다. 두 경우 모두 0을 반환해서 최대 이익을 구하는데 영향을 받지 않도록 한다.

 

복잡도 분석

백준이가 마지막으로 일하는 날을 N번째 날이라고 하자. 이때 시간복잡도와 공간복잡도는 아래와 같다.

 

시간 복잡도 : $O(n)$

이유 : 재귀함수에서 memoization table에 기록되지 않은 날들은 모두 호출되고 기록된 날들은 상수 시간안에 값을 반환하기 때문에

 

공간 복잡도 : $O(n)$

이유 : $T_i$와 $P_i$를 저장하는 배열과 memoization table에 모두 n개의 공간이 필요하기 때문에

 

코드

 

문제 출처와 원본 문서

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

14501번: 퇴사

www.notion.so/BOJ-14501-09a20ed4797748d9a90dcebe85dcaf9f

BOJ 14501 - 퇴사