백준 2579 계단 오르기 JAVA (DP)

1. 문제

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

2579번: 계단 오르기

 

2. 설명

dp배열 초기화 때문에 헤맨 문제

무조건 첫번 째 계단부터 시작해야 되는 줄 알았는데 그런 조건은 없다.

마지막 계단만 밟으면 됨.

따라서 dp[2]에 첫번 째 계단, 두번 째 계단을 밟을 경우와 첫번 째 계단, 세번 째 계단을 밟을 경우 중 최댓값을 삽입해야 한다.

 

3. 코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 계단 개수
		int[] stairs = new int[300];
		int[] dp = new int[300];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			stairs[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = stairs[0];
		dp[1] = stairs[0]+stairs[1];
		dp[2] = Math.max(stairs[0]+stairs[2], stairs[1]+stairs[2]);
		
		for(int i=3; i<N; i++) {
			dp[i] = Math.max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i]);
		}
		System.out.println(dp[N-1]);
	}
}