백준 2579번 <계단 오르기>

백준 알고리즘 2579번

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

2579번: 계단 오르기

---

2579번

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 이때, 최대 점수는 몇 점인지 구하여라.

1. 계단은 1칸 or 2칸 올라갈 수 있다.
2. 연속된 3개의 계단을 모두 밟을 수 없다.
3. 마지막 계단은 반드시 밟아야 한다.

 

입력으로 첫 줄에 계단의 개수 n이 주어지고 그 다음 줄에 n개의 각 계단의 점수가 주어진다.

 

출력으로 계단 오르기 게임을 할 때, 최대 점수는 몇 점인지 구하여라.

---

문제 해결

이 문제는 작은 문제의 답을 모아서 큰 문제의 답을 구할 수 있다. 즉, 다이나믹 프로그래밍으로 풀 수 있다.

 

계단 오르기 게임의 조건은 3개로 1번, 3번 조건을 만족하는 것은 1차원 배열로 메모제이션을 할 수 있지만 2번 조건을 위해서 2차원 배열을 사용해야 한다. (계단 점수를 저장한 배열 stairs의 index가 0부터 시작하기 때문에, 0번째 계단, 1번째 계단,,,,이렇게 간다고 하자.)

 

해당 2차원 배열을 dp라고 하자.

dp[i][j] = i번째 계단을 꼭 밟았고, 연속으로 j개의 계단을 밟았다는 의미이다.

 

dp[1][1] : 1번째 계단을 밟았고, 연속으로 1개의 계단을 밟았다.

dp[1][2] : 1번째 계단을 밟았고, 연속으로 2개의 계단을 밟았다. -> 0번째 계단과 1번째 계단을 모두 밟았다.

 

dp[i][1]는 i번째 계단을 밟아서 j가 1인 것이므로 i-1번째 계단을 밟을 수 없다. i-1번째 계단을 밟지 않았기 때문에 i-2번째 계단을 밟은 것과 i-2번째 계단과 i-3번째 계단을 밟은 것을 비교해 큰 값에 현재 계단의 점수를 더한다.

따라서 dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + stairs[i]

 

dp[i][2]는 i번째 계단을 밟아서 j가 2인 것이므로 i-1번째 계단을 밟아야 한다. 그리고 i-1번째 계단에서는 연속으로 1개의 계단을 밟아야 i번째 계단을 밟을 수 있다.

따라서 dp[i][2] = dp[i-1][1] + stairs[i]

 

이때, 0번째 계단과 1번째 계단은 미리 채우고 for문을 2부터 n-1까지 돌린다.

---

Python 코드

n = int(input())
dp = [[0, 0, 0] for _ in range(n)]
stairs = [int(input()) for _ in range(n)]
if n == 1:
    print(stairs[0])
else:
    dp[0][1] = stairs[0]
    dp[1][1] = stairs[1]
    dp[1][2] = stairs[0] + stairs[1]
    for i in range(2, n):
        dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + stairs[i]
        dp[i][2] = dp[i-1][1] + stairs[i]
    print(max(dp[n-1][1], dp[n-1][2]))

 

100%가 거의 다 됬는데 틀려서 왜지 했더니 n이 1일 경우에 대한 예외처리를 해주지 않아서 그랬다. 

---

Java 코드(22.09.26)

package boj2579;

import java.util.Scanner;
/*
 * dp를 이용해 해결
 * dp[i][0] -> i번째 계단까지 오는데 1번 연속으로 밟았다.
 * -> 그 전 계단(i-1번 계단)을 밟으면 안된다.
 * -> 그 전전 계단(i-2번 계단)을 오르는 2가지 방법(dp[i-2][0], dp[i-2][1]) 중 큰 값을 선택.
 * dp[i][1] -> i번쨰 계단까지 오는데 2번 연속으로 밟았다.
 * -> 그 전 계단(i-1번 계단)까지 오는데 1번 연속으로 밟아야 한다. -> dp[i-1][0]
 * */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] stairs = new int[N];
		for (int i = 0; i < N; i++) {
			stairs[i] = sc.nextInt();
		}

		int[][] dp = new int[N][2];
		dp[0][0] = stairs[0];
		for (int i = 1; i < N; i++) {
			if (i == 1) {
				dp[i][0] = stairs[i];
				dp[i][1] = dp[i-1][0] + stairs[i];
			} else {
				dp[i][0] = stairs[i] + Math.max(dp[i-2][0], dp[i-2][1]);
				dp[i][1] = dp[i-1][0] + stairs[i];	
			}
		}

		int answer = Math.max(dp[N - 1][0], dp[N - 1][1]);
		System.out.println(answer);
	}

}

---

결과

---