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

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int score[] = new int[301];
		int dp[] = new int[301];
		
		for (int i = 1; i <= N; i++) {
			score[i] = sc.nextInt();
		}
			
		dp[1] = score[1];
		dp[2] = score[1]+score[2];
		dp[3] = Math.max(score[1]+score[3], score[2]+score[3]);
		
		for (int i = 4; i <= N; i++) {
			dp[i] = score[i]+Math.max(dp[i-2], score[i-1]+dp[i-3]);
		}
		
		System.out.println(dp[N]);
		
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

dp[i] : i번째 계단까지 올라갔을 때 얻을 수 있는 점수의 최대치

계단을 연속으로 3개씩 밟으면 안 된다는 규칙에 의해

dp[i] = i번째 계단 점수 + max(dp[i-2], dp[i-3]+(i-1) 번째 계단 점수) 

라고 점화식을 세우고 풀이를 하였습니다.

 

 

🔗 링크

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

2579번: 계단 오르기