[알고리즘] 백준 2579 계단오르기 -dp-

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

2579번: 계단 오르기

 

 

 

 

백준 계단 오르기 dp 문제를 풀어봤습니다. ㅎㅎ  DP 가 아주 조금은 감이 오는 것 같습니다. 

문제의 포인트는 한칸 이동과 두칸 이동이 있는데 연속으로 세개의 계단을 밟을 수 없기 때문에 한칸이동을 연속 두번 할 수 없습니다.

지금까지의 누적 값을 result 배열에 담고 여기는 과거계단들의 경우의 수 중 최댓값이 들어가야합니다.

계단을 한칸밟고 올라온 경우와 그냥 두칸을 오르는 경우의 수 중 큰 값을 골라주도록 합니다. 이 때 한칸 밟고올라온 경우는 그 이전은 두칸을 무조건 띄워야하므로 해당 식도 추가 해줍니다. (이 로직을 위해서 1,2 번째 계단은 미리 초기화를 해줍니다.)

 

코드는 다음과 같습니다.

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 계단 개수
        int[] stairs = new int[n + 1];
        int[] result = new int[n + 1];
        // 계단 값 초기화
        for (int i = 1; i <= n; i++) {
            stairs[i] = sc.nextInt();
        }
        // 첫 두 계단 세팅과 2 이하의 경우 예외처리
        if (n > 2) {
            result[1] = stairs[1];
            result[2] = stairs[1] + stairs[2];
        } else {
            if (n == 1) {
                System.out.println(stairs[1]);
                return;
            } else {
                System.out.println(stairs[1] + stairs[2]);
                return;
            }
        }
        for (int i = 3; i <= n; i++) {
            // 2->1->(현재) OR  2->(현재) 중 최댓값
            result[i] = Math.max(result[i - 3] + stairs[i - 1] + stairs[i], result[i - 2]  + stairs[i]);
        }
        System.out.println(result[n]);
    }
}

 

 

 

요즘 귀차니즘이 생긴 것 같은데 열심히 해야겠습니다... 허허