[PS] 백준 2579번 계단 오르기

문제

2579번: 계단 오르기

풀이

참고한 풀이

 

앞으로는 PS 문제 푸는 방식을 바꿔보려한다.

문제풀이법이나 다양한 알고리즘에 익숙하지 않은 상태에서 문제를 풀려다 보니 시간이 오래걸리고, 해답을 보더라도 이해하는데 시간이 걸린다.

 

학창시절 수학을 잘 못하고, 싫어했던 이유 중에 하나가 안풀리는 문제가 있으면 몇시간이고 끙끙 대면서 붙잡고 있기 때문이었는데 지금 똑같은 상황을 겪고 있다 ㅎㅎ...

 

앞으로는 우선 문제에 대해서 10분간만 생각해보고 바로 해답을 보면서 풀어야겠다.

 

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //계단 수

        int[] stair = new int[301];//값
        int[] dp = new int[301]; //누적합        

        for(int i=1; i<=n; i++) //계단 점수 입력받기
            stair[i] = in.nextInt();

        dp[1] = stair[1];
        dp[2] = stair[1] + stair[2];
        dp[3] = Math.max(stair[1], stair[2]) + stair[3];

        //dp[i-3]이 식에 필요하므로 앞 세칸은 값 저장 필요                
        for(int i=4; i<=n; i++) {
            //1. n-3, n-1, n
            //2. n-2, n
            dp[i] = Math.max(dp[i-3] + stair[i-1], dp[i-2]) + stair[i];//최댓값 저장
        }

        System.out.println(dp[n]);

    }
}