백준 2579번(DP) : 계단 오르기 (JAVA) 문제 풀이

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

2579번: 계단 오르기

---

 

✏️ 문제

 

---

🔐 문제 해결

문제의 조건을 해석해보면 아래와 같습니다.

• 계단은 한번에 한칸 또는 두칸을 오를 수 있습니다.
• 연속된 세 개의 계단을 밟아서는 안됩니다.
  • 1 칸씩 세번 연속 오르면 안된다는 뜻!
• 마지막 칸은 무조건 밟아야 합니다.

 

1. 테이블 정의하기

dp[i][j]의 i는 i 번째 계단에 올랐을 때의 최대 점수의 합이 되고, j는 현재까지 몇번을 연속해서 계단을 밟고 왔는지를 뜻합니다.

그렇다면, j는 3번 연속 오르면 안되기 때문에 j의 값은 1 또는 2가 됩니다.

2. 점화식 세우기

dp[i][j]의 점화식을 세우기 전에 예를 들어 4 칸인 계단을 예를 들어서 생각해보겠습니다.

4 칸인 계단을 밟는 방법은 아래의 그림처럼 4 가지 방법이 있습니다.

• 1칸 -> 1칸 -> 2칸 이동

• 1칸 -> 2칸 -> 1칸 이동

• 2칸 -> 1칸 -> 1칸 이동 (3 계단 연속해서 밟아서 제외)

• 2칸 -> 2칸 이동

마지막 4 번째 계단을 올랐을 때의 1개의 연속된 계단을 밟았을 경우와 2개의 연속된 계단을 밟았을 경우를 나누어 볼 수 있다.

• dp[4][1] : 1개의 연속된 계단을 밟고 왔을 경우
  • 1칸, 1칸, 2칸 이동한 경우
  • 2칸, 2칸 이동한 경우

dp[4][1] = Math.max(dp[2][2], dp[2][1]) + scores[4];

• dp[4][2] : 2개의 연속된 계단을 밟고 왔을 경우
  • 1칸, 2칸, 1칸 이동한 경우

// dp[3][2]의 값을 비교하지 않은 이유는, 3 번째 계단에서 이미 2개의 계단을 연속으로 밟고 왔다면? 4 번째 계단을 밟는다면 3개의 계단을 연속해서 밟는 것이기 때문에 조건에 어긋나기 때문에 무조건 1개의 계단을 연속해서 밟은 상태여야 합니다.
dp[4][2] = dp[3][1] + scores[4];

 

초기값 설정

위의 점화식을 세울 때 봤던 그림을 이용해서 초기값을 설정한다면, 아래와 같습니다.

// 1번째 계단은 1개의 계단을 연속해서 올라 갈 수 있습니다. 하지만, 1번째 계단이기 때문에 2개의 연속해서 계단을 올라올 수는 없습니다.
dp[1][1] = 1;
dp[1][2] = 0;

// 2번째 계단은 1개의 계단을 연속해서 올라 갈 수 있습니다. 2개의 계단을 연속해서 오른다면, 이전의 계단을 밟았다는 뜻이므로 점수를 더해줍니다.(하지만 이전 계단은 반드시 1개의 계단을 밟은 상태이여야 합니다.)
if(N >=2) {
	dp[2][1] = scores[2];
    dp[2][2] = dp[1][1] + scores[2];
} // 계단의 높이가 1일 경우를 대비해서 예외처리를 해줍니다.

 

---

🗝 전체 코드

import java.io.*;

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

        int N = Integer.parseInt(bf.readLine());
        int[] score = new int[N+1];

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

        // dp[i][1]는 i번째 계단을 1계단 연속으로 올라왔다는 뜻입니다. -> i-1을 밟지 않았다는 뜻!
        // dp[i][2]는 i번째 계단을 2계단 연속으로 올라왔다는 뜻입니다. -> i-1를 무조건 밟았다는 뜻!
        int[][] dp = new int[N+1][3];

        // 초기값 세팅
        dp[1][1] = score[1];

        // 1이 입력되는 것을 방지하여 예외처리
        if(N >= 2) {
            dp[2][1] = score[2];
            dp[2][2] = score[1] + score[2];
        }

        // i번째 계단을 1연속으로 밟았다는 것은, i-2계단을 1연속으로 밟고 올라온 점수(dp[i-2][1])와, 2연속으로 밟고 올라온 점수(dp[i-2][2])중 가장 큰 점수를 선택하면 됩니다.
        // i번째 계단을 2연속으로 밟았다는 것은, i-1계단을 무조건 밟고 왔어야 하는데, i-1계단을 밟았을 당시에는 1연속으로 밟고 온 상태여야 합니다!
        for(int i=3; i <= N; i++) {
            dp[i][1] = Math.max(dp[i-2][1], dp[i-2][2]) + score[i];
            dp[i][2] = dp[i-1][1] + score[i];
        }

        System.out.print(Math.max(dp[N][1], dp[N][2]));
    }
}