[백준문제풀이] 2579 계단 오르기 java

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

2579번: 계단 오르기

 

접근법 : 

**1) 어떻게 풀 것인가?**

이 문제는 dp개념을 사용하여 풀어야한다. 

보통 dp[n]은 n에 오기까지 걸린 최대/최소값 으로 정의한다.

(이 문제는 최댓값을 찾는 문제이므로 dp[n]은 n에 오기까지 최댓값이라 정의)

 

dp란 주어진 문제를 여러개의 작은 문제로 나누어 해결하고, 기존에 해결된 문제의 해결법을 재활용하는 알고리즘이다. 

아래 그림에서 계단은 순서대로 1,2,3....의 index를 가진다고 가정한다.

 

규칙)

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 

 

위 그림을 보고 아래와 같은 사항을 이해할 수 있다.

 

1. 첫번째 계단에 올랐을때 가지는 최댓값은 첫번째 계단을 밟는 방법이다.

2. 두번째 계단을 오르는 방법에는 

(1) 처음부터 두번째 계단 밟기

(2) 첫번째계단, 두번째 계단 밟기

 

두 방법이 있는데 (2)는 항상 (1) 이상으로, 두번째 계단을 오르는 방법은 (2)번이어야한다. (조건에 계단은 자연수라고 써있음)

 

위 사항을 아래와 같이 식으로 정리 가능하다.

1. dp[1] = stairs[1]

2. dp[2] = stairs[1] + stairs[2]

 

그리고  계단이 3개 이상일때부터 규칙에 따라 dp적으로 식을 생각할 수 있다. 

 

세번째 계단에 오르는 방법에는

1. 시작지점에서 첫번째 계단을 밟고, 한칸 뛰어 세번째 계단을 밟는 경우

2. 시작지점에서 두번째 계단을 밟고 세번째 계단을 밟는 경우

이고 둘 중 더 큰값이 세번째 계단에 오르는 방법이 되어야한다.

 

라는 사항은

dp[3] 

1. dp[1] + stairs[3]

2. dp[0] + stiars[2] + stairs[3]

으로 정리할 수 있고, 이는 n으로 치환하면

 

dp[n]

1. dp[n-2] + stairs[n] // 직전 계단에서 점프O

2. dp[n-3] + stairs[n-1] + stairs[n] // 직전 계단에서 점프X

 

이 된다.

그리고 1,2 중 더 큰 값이 무엇인지 비교하여 dp[n] 에 대입하면 된다.

 

 

 

**2) 시간복잡도**

1초이다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수라는 조건이 있는데 

해당 시간복잡도는 O(N)으로 시간은 넉넉하다.

 

**3) 공간복잡도**

128mb이다.

 

**4) 풀면서 놓쳤던점**

dp에 대하여 이해 못했을때 풀었던 문제라 책을 보고 도움받아가며 풀었다. 

이후 완전히 이해하고 삼성 sds 특강에서 한번 더 문제를 풀게되었는데 전에 공부한덕에 문제를 좀 더 쉽게 풀 수 있었다. 

 

**5) 이 문제를 통해 얻어갈 것**

dp에 대한 이해

문제를 다른 방식으로 생각하기 ( 다양한 관점으로)

 

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] stairs = new int[n+1];
        stairs[0] = 0;
        for(int i =1; i<=n; i++){
            stairs[i] = Integer.valueOf(br.readLine()); 
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = stairs[1];
        if(n >=3){
            //바보다........ n=1일때 18번줄이 밖에 있으면 에러남 당연함..
            dp[2] = stairs[1] + stairs[2];
            for(int i =3; i<=n; i++){
                int nojump = stairs[i] + stairs[i-1] + dp[i-3];
                int onejump = stairs[i] + dp[i-2];
                if(nojump > onejump){
                    dp[i] = nojump;
                }
                else{
                    dp[i] = onejump;
                }
            }
        }
        else if(n==2){
            //그러므로 n이 2일때 경우를 따로 해야함
            dp[n] = stairs[1] + stairs[2];
        }
        System.out.println(dp[n]);
    }
}