백준 2579 계단 오르기 [JAVA]

문제 해석

• 문제가 요구하는 바를 간단하게 정리하면 아래와 같다.
  1. 계단을 오를 때는 3계단을 연속으로 밟을 수 없다. (연속으로 계단을 오를 수 있는 건 1~2개의 계단만!)
  2. 마지막 계단은 반드시 밟아야 한다.
• N이 6이라고 가정할 때 아래와 같은 과정을 거친다.

			[입력 값]
 			N = 6
            10
            20
            15
            25
            10
            20

            //메모제이션
            dp[0] = 0
            dp[1] = floor[1] = 10
            dp[2] = floor[1] + floor[2] = 10 + 20 = 30

            solution(6)
            dp[6] = Math.max(solution(4), solution(3)+floor[5]) + floor[6];

                solution(4)
                dp[4] = Math.max(solution(2), solution(1)+floor[3]) + floor[4]

                    solution(2)
                    dp[2] = 30

                    solution(1)
                    dp[1] = 10

                solution(4)
                dp[4] = Math.max(30, 10+15)+25 = 55 => 1번, 2번, 4번 계단 밟음

                solution(3)
                dp[3] = Math.max(solution(1), solution(0)+floor[2]) + floor[3]

                    solution(1)
                    dp[1] = 10

                    solution(0)
                    dp[0] = 0

                solution(3)
                dp[3] = Math.max(10, 0+20) + 15 = 35 => 2번, 3번 밟음

            solution(6)
            dp[6] = Math.max(55, 35+10) + 20 = 75 => 1번, 2번, 4번, 6번 밟음

코드

import javax.swing.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int[] floor;
    static int N;
    static Integer[] dp;

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

        N = Integer.parseInt(br.readLine());

        floor = new int[N+1]; //계단 개수 초기화
        dp = new Integer[N+1]; //방문여부 확인 배열

        for(int i = 1; i <= N; i++){
            floor[i] = Integer.parseInt(br.readLine());
        }

        // 비교할 때 2칸을 초과해서 연속으로 밟을 수 없다
        // 처음 계단 2개는 값을 미리 넣는다(메모이제이션)
        dp[0] = 0; //floor[0]은 쓰지 않는다 => 값 0
        dp[1] = floor[1];

        if(N >= 2){ //N이 2일때는 차피 1과 2를 모두 밟는게 최댓값일 테니...
            dp[2] = floor[1] + floor[2];
        }

        System.out.println(solution(N));

    }
    //최댓값을 구하는 솔루션
    public static int solution(int index){

       if(dp[index] == null){ //아직 방문하지 않은 경우
           dp[index] = Math.max(solution(index-2), solution(index-3)+floor[index-1]) + floor[index];
       }

        return dp[index];
    }
}

결과

느낀점

• 직접 로직을 입력하면서 확인하지 않는 이상 생각도 안나고... 이해하기 좀 어렵다😭😭
• 동적계획법 다시 공부해야할 것 같다...