2579

계단오르기

포도주 마시기와 똑같은 문제.
단, 마지막 계단을 포함한다? -> 현재 포도주를 반드시 마셔야한다와 같은 의미로 포도주에서 처럼 두번 연속 마시지 않는 경우는 고려하지 않는다(더 쉽다)

arr:  10 20 15 25 10 20 
dp : 10 30 35 55 65 75​


1)
10 

2)
10  =10
10 + 20 =30

3)

20+15 =35

10+15 =25 

4)
10 + 20 + 25 =55

10 + 15 + 25 =45
5)

10 + 25 + 30 = 65

10 + 35 = 45

6)

35 + 10 + 20 = 65
55 + 20 = 75

점화식
dp[i] = Math.max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i];

 

글로 풀어서 설명하면,

 

1칸 아래 계단을 밟았으므로 3칸 아래 계단의 최대값과 더해준다.

2칸 아래 계단에서의 최대값에서 현재 계단으로 2칸 넘어 옴.

 

둘중 큰녀석을 택한다.

 

//2579

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

   static int[] arr;
   static int[] dp;

   public static void main(String[] args) throws IOException {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      int N = Integer.parseInt(st.nextToken());
//
//      arr = new int[N + 1];
//      dp = new int[N + 1];

      arr = new int[303];
      dp = new int[303];
      for (int i = 1; i <= N; ++i) {
         st = new StringTokenizer(br.readLine());
         arr[i] = Integer.parseInt(st.nextToken());
      }

      /*Bottom-up*/
      /*
      dp[1] = arr[1];
      dp[2] = arr[1] + arr[2];
      for (int i = 3; i <= N; ++i) {
         dp[i] = arr[i];
         dp[i] = Math.max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
      }
      */
      
      /*Top-down*/
      dfs(N);
      
      /*
      for (int v : dp)
         System.out.print(v + " ");
      System.out.println();
      */
      System.out.println(dp[N]);
      br.close();

   }

   static int dfs(int n) {
      if(n < 2) {
         return dp[n] = arr[n];
      }
      if( n == 2) {
         return dp[2] = arr[1] + arr[2];
      }
      
      if(dp[n] == 0) {
         dp[n] = arr[n];
         dp[n] = Math.max( dfs(n-3) + arr[n-1], dfs(n-2)) + arr[n];         
      } 

      return dp[n];
   }

}