백준 - 계단 오르기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2579

 

[문제 설명]

 

 

[접근 방법]

다이나믹 프로그래밍 거의 첫 도전 문제고 사실 못풀어서 답지를 참고해서 풀었다.

예전에 리트코드에서 2,3문제 정도 푼 적이 있긴 하지만. 당시에 개념도 제대로 잡지 못하고, 완전탐색 같이 야매 방법으로 푼 게 많아서 사실상 처음이다.

사실 카테고리를 동적프로그래밍으로 잡아서 그렇지 완전탐색으로 충분히 풀 수 있는 문제 같다고 생각했는데 문제 조건이 계단이 최대 300개이므로 완전탐색의 경우 2^300이 나와서 시간이 무조건 초과가 나올 듯 하다.

 

우선 이 문제를 풀기 위해선, 계단을 오르는 경우의 수를 생각해야 한다.

[밟은 계단은 O, 밟지 않은 계단은 X처리했다.]

사실 이 문제는 뒤에서부터 보는 게 점화식을 유도하기가 편하다. 

마지막 계단은 무조건 밟아야 하는 조건이 있으므로  마지막 계단은 O처리를 했고, 나머지 앞에 올 수 있는 모든 조건을 다 썼다.

사실 이 두가지 패턴 말고는 올 수 있는 경우의 수가 없다.

예를 들어, ...oxo가 온다고 하더라도 ...xo가 나오는 경우의 수에 연장선이다.

 

 

이를 통해 우리는 두 가지 점화식을 유도할 수가 있다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int sizeOfStairs;
    static int[] stairs;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sizeOfStairs = Integer.parseInt(br.readLine());
        stairs = new int[sizeOfStairs];
        dp = new int[sizeOfStairs];
        // 계단 점수 입력 받기
        for (int i = 0; i < stairs.length; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }

        // 입력 받을 개수가 3개 이하면
        if (sizeOfStairs <= 3) {
            if (sizeOfStairs == 1) {
                System.out.println(stairs[sizeOfStairs-1]);
            } else if (sizeOfStairs <= 2) {
                for (int i = 0; i < sizeOfStairs; i++) {
                    dp[1] += stairs[i];
                }
                System.out.println(dp[sizeOfStairs-1]);
            } else {
                int sum = stairs[0] + stairs[2];
                sum = Math.max(stairs[1]+stairs[2],sum);
                System.out.println(sum);
            }
            
            return;
        }

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

재귀로도 충분히 풀 수 있는 문제 같아 보인다.

이번엔 카테고리를 알고 풀었는데도 많이 헤멨는데, 과연 카테고리를 몰랐을 때 간단히 풀 수 있을지 의문이 들긴 하다.

많이 풀어보는 수밖에

 

[내 답안 수정하기]

다른 사람들 답안을 봤는데, 크기가 3이하인 경우를 체크 안하기 위해 dp크기를 가능한 최대 크기로 둔 경우가 많았다.

확실히 코드가 훨씬 깔끔하긴하다. 공간복잡도도 O(n)밖에 안되므로, 괜찮아보인다.