백준 2579 계단 오르기 (Java 자바)

전형적인 DP 문제이다.

 

import java.util.Scanner;

public class bj2579_계단오르기 {
	static int dp[][];
	static int score[];
	static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		score = new int [301];
		dp = new int [301][2];
		
		for (int i = 1; i <= N; i++) {
			score[i] = sc.nextInt();
		}
		
		dp[1][0] = dp[1][1] = score[1];
		dp[2][0] = dp[1][0] + score[2];
		dp[2][1] = score[2];
		
		for(int i = 3; i <= N; i++) {
			dp[i][0] = dp[i - 1][1] + score[i];
			dp[i][1] = Math.max(dp[i - 2][0] + score[i], dp[i - 2][1] + score[i]);
		}
		
		System.out.println(Math.max(dp[N][0], dp[N][1]));
	}
}

/*
3번째 계단부터는 1,2,3 이렇게 갈 수 없다
따라서 이차원 배열을 만든 뒤, 
현재 칸에서 바로 전 칸에서 올라오는 방법 dp[i][0] = dp[i - 1] + score[i]과
현재 칸에서 전전 칸에서 두 칸 밟고 올라오는 방법 dp[i][1] = Math.max(dp[i - 2][0] + score[i], dp[i - 2][1] + score[i])이 있다.

그런데 2칸 전에서 올라오는 방법에는 예를 들어 현재 4번째 칸이라고 가정했을 때
전전칸인 2번째 칸에서 올라오는 방법은 1, 2, 4 이렇게 올라오는 방법과 2, 4로 올라오는 방법이 있다.
그러니까 이 둘 중에서 최대값을 구해서 현재 4번째 계단의 점수를 더해주면 된다.

 
*/