백준 2579 계단오르기

문제보기

문제를 살펴보면 이러하다.

1. 한번에 1~2계단 갈 수 있다. 

2. 연속3개는 밟을 수 없다. 

3. 그리고 밟았을때, 포도주 문제와 달리 선택/미선택의 결정을 할 수 없다. 

경우를 나눠보자 

첫 번째, 1개 연속 밟았을 경우 

i 번째 일때 , i-1을 밟지 못한다. 그리고 i-2번째를 밟고 올라온다 

-- > D[i-2]+A[i]

두 번째, 2개 연속 밟았을 경우 

i번째 일때, i-1을 밟아야한다. 하지만 i-2번을 밟으면 규칙에 위배되므로 밟지 않는다. 

그리고 D[i-3]을 더한다.(여기는 뭘해도 상관없다. 규칙에 영향을 안받음)

점화식은 아래와 같다. 

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

2차원 배열의 경우 점화식 : D[i][1] = Math.max(D[i-2][2],D[i-2][1])+A[i]

D[i][2] = D[i-1][1] + A[i]

Math.max(D[N][1],D[N][2])

<전체코드>

package Problems;
/**
 * 
 * 백준 2579 계단오르기 
 * 
 * 동적계획법 
 * 
 * 
 */
import java.util.Scanner;
public class Boj2579dp {
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i <=n; i++) {
            
            arr[i] = in.nextInt();
        }
        
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        for(int i = 3; i <=n; i++) {
            
            dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
            
        }
        
        System.out.println(dp[n]);
    }
}