[BJ] 백준 2579 계단 오르기 (JAVA)

문제

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

 

풀이 방법

각 계단에는 점수가 있고, 계단을 밟으면 점수를 얻을 수 있다.
대신에 한번에 최대 두 칸까지만 오를 수 있고, 연속한 세개의 계단을 밟을 수 없다.
얻을 수 있는 최대 점수를 구하면 되는 문제다.
dp를 사용해서 풀었다. dp[i]의 값은 i번째 계단은 밟는다는 것을 가정하고, i-1번째, i 번째 연속해서 밟는 경우와 i-2번째, i번째 한 칸 뛰어 넘고 밟는 경우 중에서 더 큰 점수를 가진 경우를 저장했다.
연속해서 밟는 경우는 연속 3개는 밟으면 안되기 때문에 dp[i-3]의 값을 더해줘야한다.

 

제출 코드

import java.io.*;

public class BJ_2579_계단오르기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] map = new int[N + 1];
		int[] dp = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			map[i] = Integer.parseInt(br.readLine());
		}

		dp[1] = map[1];
		if (N > 1)
			dp[2] = map[1] + map[2];
		for (int i = 3; i <= N; i++) {
			dp[i] = Math.max(dp[i - 3] + map[i - 1] + map[i], dp[i - 2] + map[i]);
		}
		System.out.println(dp[N]);
	}
}