[백준] 2579번 - 계단 오르기

 

dp문제이다. 한 번에 3개의 계단을 연속으로 오를 수 없다는 조건이 있기 때문에 이 조건에 유념하여 문제를 풀었다. 먼저 주어진 계단의 개수가 2개 이상인 경우에는 2번째 계단 까지의 값을 기본 값으로 지정해준다. 그 이후에는 두 가지 경우의 수가 있다. 첫 째는 2칸 전에서 올라오는 경우이고, 하나는 한 칸 전에서 올라오고 그 전은 두 칸을 점프한 경우이다. 이것 두 가지 값 중 큰 값을 저장해서 출력해주는 재귀함수를 작성하여 문제를 해결할 수 있다.

이 문제에서 메모이제이션이라는 기법을 사용하였는데, 작은 값들의 값을 특정 배열에 메모해두고 그 값을 이용하는 문제이다. 이 문제의 제약조건인 한 번에 3칸을 연속으로 밟지 못한다는 조건을 유념하여 메모를 할 배열에 값을 지정해나가면 해결할 수 있는 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class p2579 {
	public static int[] ary;
	public static int[] dp;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());
		ary = new int[a + 1];
		dp = new int[a + 1];

		for (int i = 1; i <= a; i++) {
			ary[i] = Integer.parseInt(br.readLine());
		}
		dp[1] = ary[1];

		if (a >= 2) {
			dp[2] = ary[1] + ary[2];
		}

		System.out.println(dp(a));
	}

	public static int dp(int a) {
		if (dp[a] == 0 && a != 0) {
			dp[a] = Math.max(dp(a - 2), dp(a - 3) + ary[a - 1]) + ary[a];
		}

		return dp[a];
	}
}