[백준-2579]-[다이나믹프로그래밍] - 계단 오르기

문제 경로 : https://www.acmicpc.net/problem/2579

이문제 같은 경우에는 점화식을 찾는데 굉장히 오래 걸렸다. 

머리가 별로 안좋은가 보다. 

굳이 점수까지 세면서 계단을 올라야 하나 좌절을 하던중 주변의 힌트와 오랜 시간의 고뇌덕에 찾았다 방법을

문제에서 제공하는 조건은 이렇다.

연속된 계단 두개는 밟을 수 있고 세개는 밟을 수 없다. 

한계단을 오른 뒤 다음다음 계단을 바로 밟을 수 있다. 

마지막 계단은 무조건 밟아야 한다.

O O X O 이런식이나 O X O O 또는 O X O X 이런식으로 계단을 밟을 수 있다.

마지막 계단은 무조건 밟아야 한다 라고 하니 아래와 같이 경우의 수 두가지가 보인다.

1. 마지막 전 계단을 밟은 경우
    이 경우는 마지막 전전 계단은 밟지 않았다는거고 전전전 계단은 밟았다는 가정이 나온다.
    그럼 마지막 계단과 마지막 전 계단의 점수의 합을 마지막 전전전 계단의 최대값과 더하면 마지막 전 계단을 밟았을 경우의 최대값이 나온다.
   
    이경우의 점화식은  SUM[N] = SUM[N-3] + array[N] + array[N-1] 으로 나온다.
   
   
   
2.  마지막 전 계단을 밟지 않은 경우
   이 경우는 마지막 전전 계단은 밟았다는 가정이 나온다. 
   그럼 마지막 전전 계단의 최대값에 마지막 계단의 점수를 더하면 마지막 전 계단을 밟지 않았을 경우의 최대값이 나온다.
   
   이 경우의 점화식은 SUM[N] = SUM[N-2] + array[N] 으로 나온다.
   
   

두 경우의 수에 나올 수 있는 점화식 두개로 값을 구하고 두 점화식 값의 최대값을 계단의 최대값을 정하면 된다.

와 구했다.. 

그전에 기본값으로 줘야하는 값들이 있었다.

첫번째 두번째 계단은 미리 기본값으로 들어가 있어줘야 다음 계단에서 계산하기 편하다. 

sum[1] = arr[1];              // 첫번째 계단을 올랐을 경우의 최대값은 하나 뿐이다.
sum[2] = arr[1] + arr[2];    // 두번째 계단을 올랐을 경우 최대값은 첫번째 두번째 모두 밟았을 경우의 수 하나뿐이다.

나머지 계단들의 최대값을 구하는 과정은 3번째 계단부터 반복문일 시도하여 위의 식으로 계산을 하면 된다.

for(int i=3; i <= cnt; i++) {
    int type1 = sum[i-2] + arr[i]; // 전계단을 밟지 않은경우 (전전 계단의 최대값에 현재 계단의 점수를 합하자)
    int type2=  sum[i-3] + arr[i-1] + arr[i]; // 전계단을 밟은 경우 (전전전 계단의 최대값과 전계단과 현재 계단의 점수를 합하자)
                
    sum[i] = Math.max(type1, type2);
}

소스

import java.util.Scanner;
 
public class E_2579 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int cnt = sc.nextInt();
        
        int[] arr = new int[cnt+1];
        int[] sum = new int[cnt+1];
        
        for(int i=1; i <= cnt; i++) {
            arr[i] = sc.nextInt();
        }
        
        sum[1] = arr[1];              // 첫번째 계단을 올랐을 경우의 최대값은 하나 뿐이다.
        sum[2] = arr[1] + arr[2];    // 두번째 계단을 올랐을 경우 최대값은 첫번째 두번째 모두 밟았을 경우의 수 하나뿐이다.
        
        for(int i=3; i <= cnt; i++) {
                int type1 = sum[i-2] + arr[i]; // 전계단을 밟지 않은경우 (전전 계단의 최대값에 현재 계단의 점수를 합하자)
                int type2=  sum[i-3] + arr[i-1] + arr[i]; // 전계단을 밟은 경우 (전전전 계단의 최대값과 전계단과 현재 계단의 점수를 합하자)
                
                sum[i] = Math.max(type1, type2);
        }
        System.out.println(sum[cnt]);
    }
 
}