백준2579 계단오르기
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩
www.acmicpc.net
개인적으로 정말 어려운 문제였다. 동적계획법은 진짜 풀이가 잘 떠오르지 않는다. 2차원 배열로 문제를 해결해야하는 것 까지는 알겠는데 그 이후로 코드를 어떻게 작성해야할지 계속 해맸다.
일단 이 문제에서 현재에 계단을 오를 수 있는 경우는 3가지이다.
1. 2칸을 오르고 1칸 오르기
2. 1칸오르고 2칸 오르기
3. 2칸 오르고 2칸 오르기
1칸을 오른 후 1칸을 오르게 되면 이미 밟고있는 계단을 포함해 연속한 3개의 계단을 밟는 것이기 때문에 문제의 조건을 어기게 된다. 이방식을 생각한 후 1칸전진하는 경우와 2칸전진하는 경우로 나누어 문제를 해결해야했다.
dp[i][0] :i번째 칸을 1칸 올라서 올라온 경우
dp[i][1]: i번쨰 칸을 2칸 올라서 올라오는 경우
dp[i][0]경우 이전에 2칸을 올라왔어야 하므로 현재위치의 값에 dp[i-1][1]을 더해준다
dp[i][1]의 경우는 이전에 1칸을 올라왔을 수도 있고 2칸을 올라왔을 수도 있으니 두값(dp[i-2][0],dp[i-2][1])중 큰 값을 선택하여 현재위치 값에 더해준다.
풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
package 동적계획법;
import java.io.*;
public class 계단오르기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] dp = new int[n + 1][2];
int[] stair = new int[n + 1];
for (int i = 1; i <= n; i++) {
stair[i] = Integer.parseInt(br.readLine());
}
dp[1][0] = stair[1];
if (n > 1) {
dp[2][0] = dp[1][0] + stair[2];
dp[2][1] = stair[2];
}
for (int i = 3; i <= n; i++) {
dp[i][0] = dp[i - 1][1] + stair[i]; // 이전에 두칸을 간 경우만 한칸을 갈 수 있기 때문에 바로dp[i-1][1] 을 더한다.
dp[i][1] = Math.max(dp[i - 2][0], dp[i - 2][1]) + stair[i];
}
if (n == 1) System.out.println(stair[1]);
else
System.out.println(Math.max(dp[n][0], dp[n][1]));
}
}
|
cs |