[BOJ 2579] 계단 오르기 (Java, DP)

 

 

---

문제 링크 

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

2579번: 계단 오르기

---

문제 풀이

- 시간복잡도 O(N)

 

 

처음 문제 풀이시 아래 (1)과 같이 점화식을 사용하여 문제 풀이를 수행했다

// i = 1, 2 일때 초기화 수행
DP[i] = DATA[i] + Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2]) 

 

이후에 더 나은 방식이 없는지 고민하던 중 예전에 구입했던 패스트 캠퍼스 강의를 확인했고,

2차원 배열을 사용하여 의미 부여를 통해 풀이하는 방식에 대해 이해 할 수 있었다.

 

	1	2	3
DP[i][0]	10	20	Math.max(DP[1][0], DP[1][1]) + DATA[3]
DP[i][1]	0	30	DP[2][0] + DATA[3]

- DP[i][0] := i -1 번째 계단을 밟지 않고, i 번째 계단에 도착하여 얻는 최대 점수

- DP[i][1] := i -1 번째 계단을 밟고, i 번째 계단에 도착하여 얻는 최대 점수 (DP[i - 1][0] + A[i])

 

- DP[i][0] 의 경우 두 계단을 뛰어 넘어서 현재 계단을 밟는 경우를 뜻함 (i - 2에서 찾아야 함)

- DP[i][1] 의 경우 이전 계단과 현재 계단을 밟는 경우를 뜻함 (이때 세 계단을 연속으로 밟는건 안된다고 명시되어 있기 때문에, DP[i - 1][0] 만이 대상이 된다)

 

https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

 

ArrayIndexOfOutBound Exception의 경우 N = 1인 경우가 있는 것으로 생각됨

---

제출 코드

(1) 점화식 사용

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;

    static int[] DP;

    static int[] DATA;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

        DP = new int[N + 1];
    }

    static void pro() {
        DP[1] = DATA[1];
        
        if(N >= 2) {
            DP[2] = Math.max(DATA[1] + DATA[2], DATA[2]);
        }

        for(int i = 3; i <= N; i++) {
            DP[i] = DATA[i] + Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2]);
        }

        System.out.println(DP[N]);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

(2) Bottom-Up 방식 

2차원 배열 활용

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] A;
    static int[][] DP;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        DP = new int[N + 1][2];
    }

    static void pro() {
        DP[1][0] = A[1];

        if(N >= 2) {
            DP[2][0] = A[2];
            DP[2][1] = A[1] + A[2];
        }

        for(int i = 3; i <= N; i++) {
            DP[i][0] = Math.max(DP[i - 2][0], DP[i - 2][1]) + A[i];
            DP[i][1] = DP[i - 1][0] + A[i];
        }

        System.out.println(Math.max(DP[N][0], DP[N][1]));
    }


    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

(3) Top-Down 방식

2차원 배열 활용

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] A;
    static int[][] DP;
    
    static void inputForTopDown() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        DP = new int[N + 1][2];
        for(int i = 0; i <= N; i++) Arrays.fill(DP[i], -1); // -1 : 방문하지 않음 의미

        DP[1][0] = A[1];
        DP[1][1] = 0;

        if(N >= 2) {
            DP[2][0] = A[2];
            DP[2][1] = A[1] + A[2];
        }

        int result = Math.max(executeByTopDown(N, 0), executeByTopDown(N, 1));
        System.out.println(result);
    }

    static int executeByTopDown(int depth, int num) {
        if(depth == 1 || depth == 2) return DP[depth][num];

        if(DP[depth][num] != -1) return DP[depth][num];

        int value = 0;
        if(num == 0) {
            value = Math.max(executeByTopDown(depth - 2, 0), executeByTopDown(depth - 2, 1)) + A[depth];
        } else if(num == 1) {
            value = executeByTopDown(depth - 1, 0)  + A[depth];
        }

        return DP[depth][num] = value;
    }

    public static void main(String[] args) throws Exception {
        inputForTopDown();
    }
    
}