[Algorithm] 계단 오르기

이번 문제는 계단을 오르는 문제다. 계단을 오르는 경우의 수 문제는 단순하게 DP를 이용하

여 해결 할 수 있다. 그러나 이번 문제는 두 가지 조건이 더 추가 되었다.

먼저 , 문제를 보자.

기존의 몇 칸 을 뛸 수 있다는 조건 외에도 연속 된 계단을 밟으면 안되고 , 마지막 계단을

무조건 밟아야 한다는 조건이 추가 되었다.

위 조건의 추가로 조금 더 생각해 보았다. 일단은 저번에 RGB거리에서 해결 했듯이 어떤

경우의 수의 최솟값 or 최댓값을 구하려면 나올 수 있는 경우의 대해서 다 구한 후

그 값들의 최솟값 or 최댓값을 구하면 되는 걸 알고 있기 때문에 나는 최댓값이 나올 수

있는 경우 들을 생각해 보았다.

나는 처음에 두가지 경우에 대해서 생각하였다.

1. N-1 번째 계단에서 올라온 경우
2. N-2 번째 계단에서 올라온 경우

위와 같이 생각 한 후 추가 된 두 조건을 계산해 보니 한 가지 경우의 수를 추가할 변수가

필요 하단 걸 깨달았다.

바로 연속상태(현재 N번째 계단에 올라 올 때 내가 연속 몇번째 계단인지)에 대한 변수다.

그렇기 때문에 위 두가지 조건을 만족하면서 생각을 해본 경우 최종 경우의 수는 다음과

같다.

1. N-1 번째 계단에서 올라온 경우 => N-1 번째 계단에서 연속 상태가 1이여야만 함
2. N-2 번째 계단에서 올라온 경우 => N-2 번째 계단에서 연속상태가 1 or 2여야함

그렇기 때문에 나는 식을 아래와 같이 세웠다.

아래와 같이 구한 두개의 값 C[N][1] , C[N][2]에 대한 최댓값을 구하면 끝 !!

소스코드:

package algorithm;

import java.util.Scanner;

public class a_2579 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] C = new int[N + 1][3];
C[1][1] = sc.nextInt();
for (int i = 2; i <= N; i++) {
int v = sc.nextInt();
C[i][1] = Math.max(C[i-2][1], C[i-2][2]) + v;
C[i][2] = C[i-1][1] + v;

}

System.out.println(Math.max(C[N][1], C[N][2]));
}

}