2017년 3월 3일 금요일

2579 계단 오르기

백준 2579 계단 오르기 : https://www.acmicpc.net/problem/2579

다음과 같은 규칙을 만족해야한다.

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

중요한 사항은 '1. 계단은 한 계단 또는 두 계단을 오를 수 있다.'
                     '2. 세개의 계단을 밟으면 안된다' 이다.

여기서 점화식의 정의를 내리면 다음과 같이 정의할 수 있다.

DP[N][M] :  M계단을 올라갈때 N번째 계단 까지의 총 점수의 최댓값 

중요사항 1번을 토대로 M은 한계단 또는 두 계단 오를 수 있으므로 [1,2] 가 된다.

중요사항 2번째에서 세개의 계단을 밟으면 안되기 때문에 M에 대한 경우를 나눠 
점화식을 완성시킨다.

1. M = 1  
한계단 올라왔을 땐 두 가지 경우로 나뉠 수 있다.
밑의 표를 보면 2번 case는 세 계단을 밟기 때문에 성립하지 않는것을 알 수 있다.
따라서 M = 1일때 N-1번째 계단을 2계단 올라온것(DP[N-1][2])에 현재 계단(Stair[N])을 더해야한다.
DP[N][1] = DP[N-1][2] + Stair[N];

2.  M = 2
두 계단 올라왔을 때도 두 가지 경우로 나뉠 수 있다.
이 경우엔 두 case 모두 성립하므로 두개중 최댓값을 구해 현재 계단과 더하면 된다.

DP[N][2] = max(DP[N-2][1], DP[N-2][2]) + Stair[N];

#include <cstdio>
#define max(a,b) ((a>b)?a:b)
int main(){
    int N, stair[301], DP[301][2= { 0 };
    scanf("%d",&N);
    for (int n = 0; n < N; n++)
        scanf("%d"&stair[n]);
    DP[1][0= stair[0];
    DP[1][1= 0;
    if (N >= 2){
        DP[2][0= stair[0+ stair[1];
        DP[2][1= stair[1];
    }
    for (int n = 3; n <= N; n++){
        DP[n][0= DP[n - 1][1+ stair[n - 1];
        DP[n][1= max(DP[n - 2][0], DP[n - 2][1]) + stair[n - 1];
        
    }
    printf("%d\n",max(DP[N][0], DP[N][1]));
    return 0;
}
cs

댓글 없음:

댓글 쓰기