백준 2579 자바 풀이

계단오르기는 Dynamic programming 초반에 가자 많이 연습하게 되는 문제입니다.

 

DP를 왜 사용할까?

DP는 기본적으로 중복으로 여러번 계산되는 것을 막기위해 고안된 방법입니다.

예를들어 파스칼의 삼각형에 경우 이항계수의 앞 계수를 구할때 사용하는 방법인데, 중복되느 경우가 있습니다

이 중복 계산이 시간을 반복적으로 잡아먹게되어 시간 초과 나는 경우가 발생합니다.

DP는 중복값이 나올때마다 이미 계산한 값이라면 계산하지 않고 값이 나오는 방식을 이용합니다.

이때, '중복 값을 미리 계산처리 하는 것'을 중점으로 두고 문제를 풀어야합니다.

 

계단 오르는 데는 다음과 같은 규칙이 있다.

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

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

 

각 계단이 마지막 계단일 경우를 상정해두고 모든 가능한 경우를 고려해보겠습니다. 이때, 최대값을 갖는 값은 arr[]로 계단값은 stairs[n]으로 가정하고 시작하겠습니다.

 

1. 첫번째 계단이 마지막인 경우 -> 경우는 stairs[1] 입니다.

 

2. 두번째 계단이 마지막인 경우 -> stairs[1]+stairs[2], stairs[2] 입니다.

단, 최대값을 구하는 것이기때문에 stairs[1]이 음수가 아닌이상 stairs[2]가 최대값이 되는경우는

없으므로 stairs[1]+stairs[2] 이 최대값이 됩니다.

 

3. 세번째 계단이 마지막인 경우 -> stairs[1]+stairs[3], stairs[2]+stairs[3] 입니다. stairs[1]+stairs[2]+stairs[3]은

위의 금지 조건 2에 해당되므로 안됩니다. 이때, 최대값은 stairs[2]+stairs[3]이 최대값이 됩니다.

 

4. 네번째 계단이 마지막인 경우 -> stairs[1]+stairs[2]+stairs[4], stairs[1]+stairs[3]+stairs[4] 입니다.

이때, 최대값은 stairs[1]+stairs[2]+stairs[4]이고 값은 55입니다.

 

여기서부터 이상한 점이 있습니다. 뭐냐하면

 

stairs[1]+stairs[2]+stairs[4], stairs[1]+stairs[3]+stairs[4] 네번째 계단의 경우의 수 부터

중복되는 경우가 있다는 것 입니다.

 

빨간 경우 대부분 두번째 경우의 수의 값을 가지게 되고, 파란 경우는 첫번째 경우의 값을 가지게 된다는 점 입니다.

이 빨간 경우에서 최대값은 stairs[1]+stairs[2] 이었죠

그렇다면 굳이 계산할 필요 없이 arr[2] 의 값을 이용하면 되겠죠

이미 계산을 했으니 필요 없는 경우인 stairs[2]+stairs[4]를 계산식에서 애초에 제거해주는 셈이 되는 겁니다.

 

다시말해 빨간 경우는 마지막 도착 지점으로 보았을때 이전에 밟은 계단이 '3번 연속으로 계단을 밟으면 안된다'는 조건 때문에 '한칸 띄워진 계단'에서 시작하는 경우라 생각하면 그 시작점에서는 갈 수 있는 경우의 수가 많을테니 그 중 최대값과 마지막 발판이 그 값이 되는 겁니다. (표현이 굉장히 애매함 차 후 수정)

 

 

파란 경우는 마지막 도착 지점으로 부터 연속으로 밟고 도착한 경우라고 생각하면 될 것 같습니다.

다시말해 연속으로 출발 해야하기 때문에, 출발 위치에서 두칸 떨어진 지점에서 두칸 떨어진 지점에서 시작을 해야합니다. (이 것도 표현 굉장히 애매..)

 

5. 다섯번째 계단이 마지막인 경우 -> stairs[1]+stairs[2]+stairs[4]+stairs[5], stairs[2]+stairs[3]+stairs[5], stairs[1]+stairs[3]+stairs[5] 이런 경우의 수가 존재하는데 역시 중복되는 경우가 발생하는걸 볼 수 있습니다.

 

stairs[1]+stairs[2]+stairs[4]+stairs[5], stairs[2]+stairs[4]+stairs[5],

stairs[2]+stairs[3]+stairs[5], stairs[1]+stairs[3]+stairs[5]

 

연두색 경우는 '두번째 계단이 마지막인 경우 선택할 수 있는 경우' 입니다. 최대값은 stairs[1]+stairs[2]입니다.

보라색 경우는 '세번째 계단이 마지막인 경우 선택할 수 있는 경우' 입니다. 최대값은 stairs[2]+stairs[3]입니다.

그렇다면 이러한 연속적 추측으로 우리가 생각 해볼 수 있는 게 있는데요.

 

첫번째는 마지막 계단과 마지막 계단의 전 계단을 밟는 경우는 마지막 계단수 -3 번째 계단 수의 최대값의 합을 구할 수 있다는 점.

두번째는 마지막 계단을 밟고 마지막 계단의 -2 번째 계단 수의 최대값의 합을 구할 수 있다는 규칙을 발견할 수 있다는 것 입니다.

 

이런 규칙성을 가지고 수식을 만들어보면

 

arr[n] = Math.max(arr[n - 3] + stairs[n] + stairs[n - 1] , arr[n - 2] + stairs[n]);

여기서 arr[]는 n번째 계단으로 도착하는 최대값을 가지는 배열입니다. stairs[]은 계단이 가지는 숫자들 입니다.

이런 규칙성을 가지고 n값을 찾아 일일히 대입해보는 코드를 짜면 아래와 같습니다.

import java.io.*;

public class t2579 {
  static int[] stairs;
  static int[] arr;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());
    stairs = new int[301];
    arr = new int[301];

    for(int i = 1; i <= T; i++) {
      stairs[i] = Integer.parseInt(br.readLine());
    }
    arr[0] = stairs[0];
    arr[1] = stairs[1];
    arr[2] = stairs[2] + stairs[1];

    bw.write(dp(T)+"");

    br.close();
    bw.flush();
    bw.close();
  }
  private static int dp(int t) {
    arr[3] = Math.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
    for(int i = 4; i <= t; i++) {
      arr[i] = Math.max(arr[i - 3] + stairs[i] + stairs[i - 1], arr[i - 2] + stairs[i]);
    }
    return arr[t];
  }
}

 

출처 : https://sundries-in-myidea.tistory.com/22