백준 2579 계단 오르기 (JAVA 자바 풀이)

백준 2579 계단 오르기 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

 

📣 출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

점화식은 생각보다 간단한데 100%에서 계속 런타임 오류가 났다.

 

입력 범위가 작은 경우 배열 초기화를 N+1로 할 경우 처리를 못하는 에러가 발생한다(e.g. 1 -> 2,3에 대한 에러) 

 

따라서 301로 배열을 초기화해주는 것으로 수정하였다.

 

 

 

💡 코드 구현

 

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

public class Main {

	private static int N;

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(bufferedReader.readLine());
		long[] stairs = new long[301];
		stairs[0] = 0;
		for (int i = 1; i <= N; i++) {
			stairs[i] = Integer.parseInt(bufferedReader.readLine());
		}

		long[] dp = new long[301];
		dp[0] = 0;
		dp[1] = stairs[1];
		dp[2] = Math.max(stairs[1] + stairs[2], stairs[2]);
		dp[3] = Math.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
		for (int i = 4; i <= N; i++) {
			dp[i] = Math.max(dp[i - 3] + stairs[i - 1] + stairs[i], dp[i - 2] + stairs[i]);
		}

		System.out.println(dp[N]);
	}
}