[백준(Baekjoon)][자바(java)] 2579 : 계단 오르기 / 동적 계획법 1

 

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

2579번: 계단 오르기

 

* 풀이 방법

-  계단은 총 N개이고, 계단을 오르는 방법은 2가지가 있으므로 N*2의 2차원 배열 생성

-  계단을 1개 오르는 경우, 그 전전 계단에서 1개/2개 오르는 경우 둘 중 더 큰 거에 더함
   2개 오르는 경우, 그 전 계단의 1개 올랐을 때의 값에 더함

 

	10	20	15	25	10	20
1개	10	20	25 (10+15)	55 (30+25)	45 (35+10)	75 (55+20)
2개	10	30 (10+20)	35 (20+15)	50 (25+25)	65 (55+10)	65 (45+20)

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), i;
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
        sc.close();
        
		int dp[][] = new int[n][2];
		for( i = 0; i < n; i++ ) {
			dp[i][0] = a[i] + ( i >= 2 ? Math.max( dp[i-2][0], dp[i-2][1] ) : 0 );
			dp[i][1] = a[i] + ( i >= 1 ? dp[i-1][0] : 0 );
		}

		System.out.println( Math.max( dp[n-1][0], dp[n-1][1] ) );
		
	}
}