백준 2579(계단 오르기) -Python(파이썬),Java(자바) - DP

2579번: 계단 오르기

예제 풀이

마지막 계단(i=5)에서의 최댓값이 나오는 가지수는 다음과 같다

  1️⃣ i=2(5-3)일때의 최댓값 + ( i=4 ) + ( i=5 )

  2️⃣ i=3(5-2)일때의 최댓값 + ( i=5 )

이 두가지를 비교해서 최댓값을 구하면 된다. 

dp[i]	0	1	2	3	4	5
i번째일 때의 최댓값	10	10+20 =30	10+15,20+15 중 큰 값= 35	dp[3-3]+(i=2)+ (i=3), dp[3-2]+(i=3) 중 큰 값 = 55	dp[4-3]+(i=3)+ (i=4), dp[4-2]+(i=4) 중 큰 값 = 65	dp[5-3]+(i=4)+(i=5), dp[5-2]+(i=5) 중 큰 값 = 75

문제 풀이

① dp[0] = array[0], dp[1] = array[0]+array[1], dp[2] = max(array[0]+array[2], array[1]+array[2])
단, n >0, n>1 , n>2라는 조건을 지정해줘야 인덱스 에러가 나지않는다. ( dp를 n개의 배열이라고 지정하였으므로)
② n이 3이상일 경우 dp[i] = max( dp[i-3] + array[i-1]+array[i] , dp[i-2]+array[i] )라는 점화식을 써준다.

💻 Python(파이썬)

import sys
n = int(sys.stdin.readline())
array = [int(sys.stdin.readline()) for _ in range(n)]
dp =[0]*(n)
if n>0:
    dp[0] = array[0]
if n>1:
    dp[1] = array[0]+array[1]
if n>2:
    dp[2] = max(array[0]+array[2],array[1]+array[2])
for i in range(3,n):
    dp[i] = max(dp[i-3]+array[i-1]+array[i],dp[i-2]+array[i])
    
print(dp[n-1])

💻 Java(자바)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N];
        int[] dp = new int[N];

        for(int i=0;i<N;i++){
            array[i] = Integer.parseInt(br.readLine());
        }
        if(N>0) dp[0] = array[0];
        if(N>1) dp[1] = array[0]+array[1];
        if(N>2) dp[2] = Math.max(array[0]+array[2],array[1]+array[2]);
        for(int i=3;i<N;i++){
            dp[i] = Math.max(dp[i-3]+array[i-1]+array[i],dp[i-2]+array[i]);
        }
        System.out.println(dp[N-1]);
    }
}