[백준] 계단 오르기 Java

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

2579번: 계단 오르기

 

 

풀이

 

문제에 나타난 조건 2개

1. 계단은 한 번에 1칸 혹은 2칸 이동 가능

2. 3칸 연속으로 밟기 불가능

 

 

 

2개의 조건을 만족하며 N 번째 계단을 밟기 위해서

 

1. N-3 을 밟고 N-2 를 건너 뛰고 N-1, N 밟기

2..N-2 를 밟고 N-1 을 건너뛰고 N 밟기

 

이렇게 두 가지 경우가 존재 >> 연속 3개의 계단은 못밟기 때문

따라서 위 2가지의 값 중 큰 값 + N 번째 계단의 점수를 더한 값이 N 번째 계단의 점수 최대값

 

각 계단의 점수를 저장하고 있는 input 배열

N번째 계단의 최대점수를 기록하는 dp

 

dp[N] = Max(dp[N-2], dp[N-3]+input[N-1]) + input[N]

라는 점화식 도출

 

 

    public void solution2579() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());


        int input[] = new int[n+1];
        int dp[] = new int[n+1];

        for(int i = 1; i<=n; i++)
            input[i] = Integer.parseInt(reader.readLine());

        dp[1] = input[1];

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


        for(int i=3; i<=n; i++)
            dp[i] = Math.max(dp[i-2], dp[i-3]+input[i-1])+input[i];

        System.out.println(dp[n]);
    }