파이문

2579. 계단 오르기 본문

문제 풀이/BOJ

2579. 계단 오르기

민Z 2017. 11. 12. 16:45
728x90

2579. 계단 오르기

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



문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.

1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.)


계단이 4개 있을 때로 문제를 늘리면 


1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])

2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4])


왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보면 이해할 수 있을 것이다.

import java.util.Scanner;

public class Main {

    public int problem2579(int[] stairs) {
        if (stairs.length == 1) {
            return stairs[0];
        } else if (stairs.length == 2) {
            return stairs[0] + stairs[1];
        }

        int[] dp = new int[stairs.length];
        dp[0] = stairs[0];
        dp[1] = stairs[0] + stairs[1];
        dp[2] = Math.max(dp[0] + stairs[2], stairs[1] + stairs[2]);

        for (int i = 3; i < stairs.length; ++i) {
            dp[i] = Math.max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i]);
        }
        return dp[stairs.length - 1];
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int stairCount = sc.nextInt();
        int[] stairs = new int[stairCount];
        for (int i = 0; i < stairCount; ++i) {
            stairs[i] = sc.nextInt();
        }
        System.out.println(main.problem2579(stairs));
    }
}


'문제 풀이 > BOJ' 카테고리의 다른 글

2293. 동전 1  (0) 2017.11.12
11053. 가장 긴 증가하는 부분 수열  (0) 2017.11.12
1149. RGB 거리  (0) 2017.04.04
1463. 1로 만들기  (0) 2017.04.03
1003. 피보나치 함수  (0) 2017.04.03
Comments