0422 TIL
DP 초보자의 좌충우돌! 우당탕탕! 기록
👉 퇴사2
위 문제를 풀면서(아직 성공 몬했지만🥲) 한 의식의 흐름 기록이랄까요..
이 모든 것에 초기 접근법으로 가는 과정, 식을 세우는 과정, 디버깅하는 과정, 약 두시간만에 처음 접근대로 가면 안되는 걸 깨달은 과정이 다 녹아있습니다 하하하!
막판에 다른 풀이를 보다가 문득 느낀 게.. DP는 다른 풀이를 봐봤자 아이디어가 전부라 내가 그 아이디어를 생각하지 않는 이상 별 의미가 없는 거 같다는 것..? 무슨 말이냐면.. 아이디어를 생각해내는 과정을 거쳐서 나만의 딱 떨어지는! 깔끔한! 식이 나와야한다는 것?!
결론: 아예 다른 접근법을 좀 더 생각해봐야 할 거 같다
(일단 2차원 배열로 가면 안된다는 건 확실히 알았어)
아직 DP의 길은 멀고도 험해 보인다..⭐️
원인: 메모리 초과 - 2차원 배열로 갈 경우 최악의 경우 1500000*1500000이기 때문
그동안 시간복잡도는 고려했어도 공간 복잡도는 고려 못했던 거 같다. 일차원 배열로 풀 수 있는 DP 접근법 생각해볼 것!!
#퇴사2
def get_max_profit(n, works):
dp = [[0]*(n+1) for _ in range(n)]
#dp[i][j]: i를 시작으로 잡았을 때, 스탭 j에서의 profit 값
dp_results = []
for i in range(n):
j = 0
cur_day = i #시작일 설정
while cur_day < len(works) and cur_day + works[cur_day][0] <= n:
dp[i][j+1] = dp[i][j] + works[cur_day][1]
cur_day += works[cur_day][0]
j += 1
dp_results.append(dp[i][j])
return max(dp_results)
n = int(input())
works = []
for _ in range(n):
a, b = map(int, input().split())
works.append((a, b))
print(get_max_profit(n, works))
#메모리초과 -> 아예 다른 접근법으로 가야한다! (2차원 배열로 갈 경우 1500000*1500000이기 때문)