[Java/백준/DP] 2579번: 계단 오르기

문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

참고

www.youtube.com/watch?v=EKHFu9vB-Oc

문제에 대한 풀이는 아니지만 계단오르기 문제 유형에 대한 감을 잡기에 좋았다.

 

코드

한칸 또는 두칸을 이동하는 것, 최댓값을 구하는 것은 어렵지 않았지만 연속된 세 개의 계단을 밟으면 안된다는 조건이 까다롭다ㅠ

 

가장 마지막 계단 N번째 계단으로 생각해본다.

그 전의 N-1번째 계단을 밟고 올라왔는지, N-2번째 계단을 밟고 올라왔는지로 나눠 계산할 수 있다. (계단은 하나 또는 두 계단씩 오를 수 있다 했기 때문)

 

1) N-1번째 계단을 밟았을 경우

 

N-3     N-2      N-1      N                  (진한 곳이 밟은 곳)

 

연속된 세 계단을 밟을 수 없다 했으므로 N-1번째 계단 전 단계는 점프를 했을 것이다.

이 경우의 점화식은,

dp[i] = stair[i] + stair[i-1] + dp[i-3];

으로 세울 수 있다.

 

2) N-2번째에서 N번째로 점프했을 경우

 

N-2      N-1      N

 

dp[i] = dp[i-2] + stair[i]

점화식은 i번째 계단의 값과 i-2번째 계단에서의 최대값의 합이다.

 

※ 주의 ※

해당 코드에서 N==1일 경우도 고려해줘야 한다.

마지막에 N==1인 테스트케이스가 있었는지 런타임에러가 계속 떴었음 ㅠ

 

 

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

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[] stair = new int[N+1];
		int[] dp_stair = new int[N+1];
		
		for(int i=1; i<=N;i++) {
			stair[i] = Integer.parseInt(br.readLine());
		}
		
		
		dp_stair[1] = stair[1];
		if(N!=1) {
			dp_stair[2] = stair[1] + stair[2];
			
			for(int i=3; i<=N; i++) {
				int jump = stair[i] + dp_stair[i-2];
				int no_jump = stair[i] + stair[i-1] + dp_stair[i-3];
				
				dp_stair[i] = Math.max(jump, no_jump);
			}
		}
		
		bw.write(Integer.toString(dp_stair[N])+"\n");
		bw.flush();
	}
}