BOJ] 2579. 계단오르기

BOJ]2579.계단오르기

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

2579번: 계단 오르기

DP는 고민하고 또 고민해야한다. 점화식(규칙)을 찾아야한다!

문제에서의 아래 규칙을 고려하여 점화식을 구해야한다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

규칙을 봤을 때, k번째 계단을 갈수 있는지 없는지 고려하는 방법을 생각해야했다.
그래서 2차원배열의 2번째 col의 index에 규칙을 주었다.
index 0은 한번 더 밟을 수 있는 값을 넣기.
index 1은 이미 연속해서 두번째 밟은 값을 넣기.


즉, memo[k][0]이 의미하는 것은 k번째 계단까지 얻은 최댓값인데, 처음 밟은 계단이므로, k+1번째에서 이 값을 활용할 수 있다.
memo[k][1]이 의미하는 것은 역시 k번째 계단까지 얻은 최댓값인데, 이미 두번연속 밟았으므로 k+1번째에서 이 값을 쓸 수 없다.
라는 것이다.

k+1번째를 생각해보자.
memo[k+1][1]은 memo[k][0]의 값과arr[k+1]의 값을 더한 값이 된다. (연속으로 밟았을 때의 값)
다음, memo[k+1][0]은 처음 밟은 값을 저장해야 하는데, 바로 이전 값(k)번째 값은 참고할 수 없다.


그러므로, 2번째 전 계단의 값을 참고해야 하는데, 이 떄는 2번째 전 계단의 값 중 최댓값을 가져오면 된다.
즉, memo[k+1][0]은 memo[k-1][0] 과 memo[k-1][1]중 큰 값이 들어가게 되는 것이다.

위 규칙을 고려하여 index 0과 1을 나눠서 흐름을 따라가보면 이해가 될 것이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public class bj_2579_계단오르기 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int[] arr = new int[N];         int[][] memo = new int[N][2];                  for(int i=0; i<N; i++)             arr[i] = sc.nextInt();                  // 2번째 col의 의미         // 0:한번더밟을수있음         // 1:연속해서못밟음(이미 두번연속 밟음)         memo[0][0]=arr[0];         if(N!=1) {             memo[1][0]=arr[1];             memo[1][1]=arr[0]+arr[1];         }         for(int i=2; i<N; i++) {             for(int j=0; j<2; j++) {                 if(j==0) {                     memo[i][j] = Math.max(memo[i-2][0], memo[i-2][1]) + arr[i];                 }                 else {                     memo[i][j] = memo[i-1][0] + arr[i];                 }             }         }         System.out.println(Math.max(memo[N-1][0], memo[N-1][1]));     } }   Colored by Color Scripter

cs