[백준]2579.계단오르기(DP)/Java

📃계단오르기

👩🏻‍💻풀이

public class Stairs_2579 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int total = Integer.parseInt(br.readLine());
		int[] DP = new int[total + 1];
		int[] stair = new int[total + 1];

		for (int i = 1; i < total + 1; i++) {
			stair[i] = Integer.parseInt(br.readLine());
		}

		DP[1] = stair[1];

		if (total >= 2) {
			DP[2] = stair[1] + stair[2];
		}

		for (int n = 3; n <= total; n++) {
			DP[n] = Math.max(DP[n - 2], DP[n - 3] + stair[n - 1]) + stair[n];
		}

		System.out.println(DP[total]);
	}

}

마지막 도착 계단은 무조건 밟아야 하므로 전 계단을 밟으면 n-3, n-1, n 을 밟아야 하고, 전 계단을 안 밟는다면 n-2, n을 밟는다. 이 두가지 경우중 큰 점수를 선택하여 배열에 저장해준다.