백준 알고리즘: 2579번 계단 오르기

문제 정보

---

 

2579번: 계단 오르기

 

핵심

---

DP(Dynamic Programming) 을 활용하여 풀이하여야 함

- Top-Down 풀이 (Recursive)

- Bottom-Up 풀이 (반복)

 

먼저 풀이하기 전에, 문제의 특성을 분석해 보았다

1. 한번에 한 계단 혹은 두 계단을 오를 수 있음

2. 연속으로 한 계단을 세번 오를 수 없음

3. 마지막 계단을 반드시 밟아야 함

 

Specification

dp[i]: 규칙을 지키며 i번째 계단을 밟았을 때의 최대값
scores[i]: i번째 계단을 밟았을 때 얻는 점수
numberOfStair: 총 계단의 수(마지막에 밟아야 하는 계단)

 

Bottom-Up을 활용한 풀이의 알고리즘

i = 1:
	scores[1]
i = 2:
	scores[1] + scores[2]
i >= 3:
	// 직전 계단을 밟는 경우, 안밟고 오는 경우 중 최대값
    Max(scores[i-1] + dp[i-3], dp[i-2]) + scores[i]
    // 직전 계단을 밟고 온다면, 그 전 계단은 밟지 않아야 한다 (3연속 X)
    // 따라서 3개 전 계단을 밟는 최대 점수 dp[i-3]
    // 1개 전 계단의 점수 scores[i-1] 를 더해준다

 

Top-Down을 활용한 풀이의 알고리즘

solution(int n) {
	dp[n]을 아직 구하지 않았다면 :
		dp[n] = Max(solution(n-3) + scores[n-1], solution(n-2)) + scores[n];

	return dp[n];
}

 

풀이

---

Bottom-Up(반복) 을 통한 풀이

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numberOfStair = Integer.parseInt(br.readLine());
        int[] scores = new int[numberOfStair + 1];
        int[] dp = new int[numberOfStair + 1];
        for (int i = 1; i <= numberOfStair; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = scores[1];
        if (numberOfStair >= 2) {
            dp[2] = scores[1] + scores[2];
        }
        for (int i = 3; i <= numberOfStair; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3] + scores[i - 1]) + scores[i];
        }
        System.out.println(dp[numberOfStair]);
    }
}

 

Top-down(재귀)를 활용한 풀이

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

class Main {
    static Integer[] dp;
    static int[] scores;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numberOfStair = Integer.parseInt(br.readLine());
        scores = new int[numberOfStair + 1];
        dp = new Integer[numberOfStair + 1];
        for (int i = 1; i <= numberOfStair; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        dp[0] = scores[0];
        dp[1] = scores[1];
        if (numberOfStair >= 2) {
            dp[2] = scores[1] + scores[2];
        }
        System.out.println(solution(numberOfStair));
    }

    static int solution(int n) {
        if (dp[n] == null) {
            dp[n] = Math.max(solution(n - 2), solution(n - 3) + scores[n - 1]) + scores[n];
        }
        return dp[n];
    }
}

 

고찰

---

해당 문제는 규칙을 관계로 옮기는 방법에 대하여 많은 고민을 하게 만들었고, 결국 스스로 이러한 아이디어를 떠올리는 데에는 실패했지만

다음에는 이와 같은 문제를 풀게 되면 다양한 관점에서 문제에 대한 접근을 해야겠다고 생각했다

무작정 작성하는 코드보다는, 보다 효율적인 방식이 중요하다는 것을 다시금 깨닫고 있다

Dynamic Programming 관련 문제를 많이 풀어 보아야 겠다

 

Reference

---

 

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

 

 

Source Code on GitHub

---