[백준] 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. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

---

풀이

 

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]);
    }
}

---

뭔가 막히면 거기서 사고가 꼬여버려서

찬찬히 컴퓨터 입장이 돼서 처리하는 순서를 돌아보도록 해야겠다.