DP - 2579_계단 오르기

2579번: 계단 오르기 (acmicpc.net)

2579번: 계단 오르기

계단오르기 문제입니다. 이 문제는 이전에 풀었던 포도주 문제와 유사했던 문제였습니다. 

1,2,3번째 일경우에는 계단 오르기 규칙에 맞게 풀면되었고 나머지 경우에는 무조건 마지막 계단수를 밟아야 한다는 규칙에 따르도록 마지막 계단 + 마지막 전 계단 + 마지막 계단 -3 계단 수의 최대값을 구한 값 혹은 마지막 계단 + 마지막 계단 + 마지막 계단 -2 위치에서의 최대값 둘중 더 큰 값을 구해나가면 됩니다. 

 

 

package com.company;

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

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


        for (int i = 0; i < t; i++) {
            number[i] = Integer.parseInt(br.readLine());
        }


        dp[0] = number[0];
        if(t>1){ dp[1] = number[0]+ number[1];}
        if(t>2){dp[2] = Math.max(number[0],number[1]) + number[2];}
        for(int i=3; i<t; i++){
            dp[i] = Math.max(dp[i-2] +number[i] ,dp[i-3] + number[i]+number[i-1]);
        }
        System.out.println(dp[t-1]);
    }
}

 

 

DP - 2156(포도주 시식) :: 꿈을 보는 개발자 (tistory.com)

DP - 2156(포도주 시식)

 

해당 문제와 연계해서 풀어도 좋은 문제입니다.