[백준] DP - 2579번, 계단 오르기 (다른 풀이 도움)
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
풀이
1. 시작점 index = 0
2. 점화식 : Math.max(d[i-2], d[i-3]+arr[i-1]) + arr[i]
3. 초기값 : d[1] = arr[1]
표를 그리면 점화식을 도출할 수 있다.
(i = 2) d[2] = arr[1] + arr[2]
| 10 | 20 |
| o | o |
...
(i = 4) 현재 값을 기준하여 볼 때, (2번째 전의 누적값 || 3번째 전의 누적값 + 직전 값) + 현재값 의 경우의 수가 나온다.
| 10 | 20 | 15 | 25 |
| o | o | x | o |
| 10 | 20 | 15 | 25 |
| o | x | o | o |
참고 (처음의 망한 풀이)
일전의 스티커나 와인 문제 풀었던 것처럼
Math라이브러리 사용해 <이전 값과 2번째 전값의 누적값 중 max값>을 비교해야겠다 생각했다.
- d[i] = Math.max(d[i-1], d[i-2]) + arr[i]
이렇게 하면 연속해서 오를 때는 되어도, 1개 skip할 때 직전 값을 놓친다.
왜인지, 여기서 막히니까 생각이 꼬여서 더이상 사고가 안 되더라... 집중력이 떨어진 탓도 있을 것 같다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
int[] d = new int[n+1];
for(int i=1; i<n+1; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
d[1] = arr[1];
if(n > 1) {
d[2] = arr[1] + arr[2];
}
for(int i=3; i<n+1; i++) {
d[i] = Math.max(d[i-2], d[i-3]+arr[i-1]) + arr[i];
}
br.close();
System.out.println(d[n]);
}
}뭔가 막히면 거기서 사고가 꼬여버려서
찬찬히 컴퓨터 입장이 돼서 처리하는 순서를 돌아보도록 해야겠다.