[백준] 2579 계단 오르기 (JAVA)

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

2579번: 계단 오르기

풀이

 나는 DP에 자신있다고 생각했는데 오만이였다. 나는 문제에 접글할때 재귀가 아닌 반복문으로만 생각을 하였고 이는 나를 오답으로 이끌었다. 사실 약 5달전에 풀어보았던 문제지만 다시 공부를 하며 풀어보았다. 그러나 생각대로 풀리지는 않았다. 조금더 공부에 신경을 써야 할것 같다.

 알고리즘에 대하여 알아보기전 풀이에 도움을 받은 블로그에 대해서 링크를 남기겠다.

https://st-lab.tistory.com/132

[백준] 2579번 : 계단 오르기 - JAVA [자바]

핵심 알고리즘은 다음과같다

dp[x] = arr[x] + Math.max(arr[x-1]+find(x-3), find(x-2))

 우선 현재 위치가 x라고 했을때 x-1을 호출할때 재귀적으로 부르면 이는 연속된값인지 아닌지 알길이 없다. 그래서 arr[x-1]을 더할때는 find(x-3)을 더하여 중복이 되는경우를 미연에 방지를 하였고 만약 dp[n-2]를 한다 하면 이는 연속이 되든 안되든 상관이 없기에 단순히 재귀로 find(x-2)를 해준다.

 나는 이 문제를 풀때 현재위치에서는 몇번째로 연속이 되었는가에 신경을 써서 틀렸던것 같다.

코드

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

class Main{


    public static int arr[];
    public static Integer dp[];
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n+1];
        dp = new Integer[n+1];

        for(int i=1; i<=n; i++){
            arr[i]=Integer.parseInt(br.readLine());
        }
        dp[0] = arr[0];
        dp[1] = arr[1];

        if(n>=2)
            dp[2]= arr[1]+arr[2];

        System.out.println(find(n));
    }

    public static int find(int x){
        if(dp[x]==null)
            dp[x] = arr[x] + Math.max(arr[x-1]+find(x-3), find(x-2));
        return dp[x];
    }

}