[studylog] DP 뽀개기의 길은 험하구나..

개발새발log·2022년 4월 22일
0

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이기 때문)
profile
⚠️ 주인장의 머릿속을 닮아 두서 없음 주의 ⚠️

0개의 댓글