[DP&백트래킹] 퇴사 - 백준 14501번

1 분 소요

Untitled

최근 백트래킹 문제를 많이 풀어서 그런가 문제를 보자마자 경우의 수 구하면 되지 않나 싶은 생각이 들었다. 뭔가 풀면서도 시간 복잡도를 계산하면서 찜찜한 기분에 풀긴 했지만 실버 단계 문제라 문제가 여유롭게 내준 것 같다.

DP 공부가 필요하다.

풀이 (백트래킹)

Untitled 1

EX)

1일 → 4일 → 5일 ⇒ 45

1일 → 5일 ⇒ 25

2일 ⇒ 20

3일 → 4일 → 5일 ⇒ 45

3일 → 5일 ⇒ 25

…

Untitled 2

점화식을 사용
- 작업을 수행하지 않는 경우:
  - dp[i + 1] = max(dp[i + 1], dp[i])
  - i번째 날까지의 최대 수익을 다음 날로 전달
- 작업을 수행하는 경우:
  - dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i])
  - 이전에 계산했던 값(다른 경우의 수) 와 i날을 선택하게 되었을 때 얻는 수익을 비교하여 최대 수익으로 대체

백트래킹 알고리즘은 가능한 모든 작업 조합을 시도하므로, 최악의 경우 지수 시간복잡도를 갖습니다. 각 작업에 대해 두 가지 선택(선택하거나 선택하지 않거나)이 존재하므로 총 경우의 수는 2^N개가 됩니다. 여기서 N은 작업의 수입니다.

동적 계획법 알고리즘은 각 날마다 얻을 수 있는 최대 수익을 저장하여, 중복 계산을 피하면서 효율적으로 최대 수익을 찾습니다. DP 배열을 채우는 과정에서 각 날마다 최대 수익을 계산하므로, 시간복잡도는 각 날을 한 번씩 처리하는 것과 같습니다.