[문제풀이] B2579 계단 오르기

계단 오르기

---

  🪅. dp(동적 프로그래밍)을 구현할 줄 아느냐 => '메모이제이션**'
  🪅. 문제의 조건에 맞는 정확한 '점화식'을 세울 수 있느냐 => 1일때부터 조건에 맞는 답을 구해본다.
  🪅. 점화식을 만들기 위해 1부터 몇 개까지 값에 대한 정의를 해야하는지 알 수 있는가? => 몇개부터가 이전의 기록으로 해결할 수 있는가를 본다. 

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

  public class B2579_계단오르기 {
      static int N;
      static int[] steps;
      static int[] M = new int[301];
      public static int dp(int x) {
          if(x == 1) return M[1] = steps[1];

          if(x == 2) return M[2] = steps[1] + steps[2];
          if(x == 3) return M[3] = Math.max(steps[1], steps[2]) + steps[3];


          if(M[x] != 0) return M[x];

          return M[x] = steps[x] + Math.max(dp(x-2), dp(x-3)+steps[x-1]);
      }
      public static void solution() {
          System.out.println(dp(N));
      }
      public static void init() throws NumberFormatException, IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          steps = new int[N+1];
          for(int i = 1; i < N+1; i++) {
              steps[i] = Integer.parseInt(br.readLine());
          }
      }
      public static void main(String[] args) throws NumberFormatException, IOException {
          init();

          solution();
      }
  }

💡. 문제 접근 과정
: 처음에는 완전탐색 문제인줄 알았다. 완전탐색 중 부분집합(선택0 or 선택x)을 문제의 조건에 맞게 구하고,
그 중, 점수의 합계가 가장 큰 것을 출력하는 방식으로 풀었으나, 메모리 초과 에러가 났다.
(계단이 최대 300개 되는데, 이를 부분집합으로 풀면 2의 300승의 경우의 수가 나온다.)
메모리 초과나, 시간초과가 날때 항상 dp(동적프로그래밍)를 생각해보는데,
계단이 한 개일부터 시작해서 score가 최대인 경우를
기록해두는 '메모이제이션'을 이용하면 되겠다는 생각이 들었다.

점화식을 세우기 위해 다음과 같은 그림을 그렸고, 이 그림에서 4번째부터 이전 1~3번째까지의 기록을 가지고
풀 수 있겠다는 생각을 할 수 있었다. 따라서 4번째부터 문제에 조건에 맞는 점화식을 세울 수 있었다.