2579 - 계단 오르기(DP, 점화식)

2579 - 계단 오르기(DP, 점화식)

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Scanner; public class Main { static Integer dp[]; static int arr[]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); dp = new Integer[1]; arr = new int[1]; for(int i = 1; i <= n; i++) { arr[i] = in.nextInt(); } dp[0] = arr[0]; // 디폴트값이 null이므로 0으로 초기화 해주어야한다. dp[1] = arr[1]; if(n >= 2) { dp[2] = arr[1] + arr[2]; } System.out.println(find(n)); } static int find(int n) { if(dp[n] == null) { dp[n] = Math.max(find(n - 2), find(n - 3) + arr[n - 1]) + arr[n]; } return dp[n]; } }

어제 풀었던 문제와 흡사한 메모이제이션 코딩입니다.

메모이제이션이란 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. 동적 계획법의 핵심이 되는 기술로서 DP를 푸는 사람들에겐 꼭 알아두어야 할 기술이라고 할 수 있겠습니다.

원래 dp[n]은 0일 때(방문하지 않은 dp값) dp[n]을 구하면 되겠으나 그렇게 될 경우 연산 속도가 느려지기 때문에 dp[n]이 null인(dp는 Integer로 선언했으므로 null일 때) 값에 대해서 dp의 max값을 구하면 되겠습니다.

이 문제의 정답률이 이렇게나 낮은 이유는 아마 순차적으로 n에 값을 더해서 그런 것이라 사료됩니다.

하지만 그렇게 풀이하면 안되고 n-2인덱스에서의 크기와 n-1, n-3, n의 값을 더한 값에서의 크기를 서로 비교하여 큰 값에 대해서 dp에 값을 저장해야 합니다. 그러니까, 연속적으로 세 개의 값이 들어가면 안되는 것을 잘 인지하고 계신다면 결국 들어갈 값은 1,2가 연속으로 들어간 값과 find(n-3)의 값과 find(n-2)의 값을 비교해주시면 되겠습니다.

결국 재귀함수를 제대로 이해하고 있어야 한다는 뜻인데, 여기서 arr[n]과 arr[n-1]과 더해진 find(n-3)의 값은 또다시 find(n-5)와 find(n-6) + arr(n-3) + arr(n-4)의 값 중 더 큰 값이 됩니다. 이런식으로 n이 1이 될 때 까지 값을 다 더하여 max에 담아 출력하시면 되겠습니다.

from http://codingrapper.tistory.com/58 by ccl(A) rewrite - 2021-10-20 01:28:07