'계단오르기' 태그의 글 목록

🚀접근하기 다이나믹 프로그래밍 문제. 사실 전부터 다이나믹 프로그래밍 문제를 어려워했었는데, 역시나 이번에도 오랜만에 하니 어려웠다..... 처음에는 정말 이상하게 접근하다가, 계단이 4개 이상일 때부터 일정한 점화식이 세워짐을 알게 되었다. 마지막 계단(n) 을 기준으로 2가지의 경우가 생기는데, 1) n과 n-2 계단 선택 2) n과 n-1, n-3 계단 선택 즉, 예제 입력대로 6개의 수가 10,20,15,25,10,20 순으로 배열에 입력되었을 때, 마지막인 6번째 계단을 기준으로 1) 6번째 계단과 4번째 선택한 경우 2) 6번째 계단과 5번째, 3번째 계단을 선택한 경우 이렇게 두가지이다. 이 둘 중 max 값을 선택하여 더해주면 된다. 점화식: dp[n] = stairs[n] + max(st..

알고리즘 2023. 9. 19. 01:44

이전 1 다음