[BOJ][ZOAC 2019]18244번 - 변형 계단 수

 

 

한양대학교 ERICA 알고리즘 연구학회 영과일의 내부 대회 "ZOAC 2019"의 문제 출제 및 검수를 맡게 되었습니다.

 

그중 G번 문제인 변형 계단 수에 대한 풀이입니다.

 

목표

문제 화면 캡쳐

기존에 백준에 있던 계단 수 문제에 조건을 하나 추가시켜 변형시킨 문제다. 풀이 방법은 기존의 계단 수에서 새로운 조건을 추가시켜 주면 된다.

 

계단 수를 간략하게나마 풀이한다면 DP[계단 수 길이][마지막 자리 수]이다. 즉, ~~~~[0-9]의 끝 자리만 저장한 뒤 다음 DP에 더해 줄 때 끝자리±1의 끝 자리에 더해주면 되는 것이다．

• DP[i][N] = DP[i-1][N-1] + DP[i-1][N+1]

변형 계단 수는 여기에 더해서 지금까지 얼마큼 연속으로 증가/감소했는지에 대한 정보를 추가적으로 갖고 있는다.

• DP[변형 계단 수 길이][마지막 자리 수][현재까지의 증감]
  • 현재까지의 증감
    • 1(3-2)  : 연속 두 번 감소
    • 2(3-1)  : 연속 한 번 감소
    • 3        : 연속 증감 X
    • 4(3+1) : 연속 한 번 증가
    • 5(3+2) : 연속 두 번 증가

를 사용하여 DP식을 전개해 나가면 된다.

 

점화식은

• DP[i][N][1] = DP[i-1][N+1][2]
• DP[i][N][2] = DP[i-1][N+1][4] + DP[i-1][N+1][5]
• DP[i][N][4] = DP[i-1][N-1][1] + DP[i-1][N-1][2]
• DP[i][N][5] = DP[i-1][N-1][4]
• 0일 경우는 ~1 -> ~10으로 가는 감소 밖에 없다. (예외 처리)
• 9일 경우는 ~8 -> ~89로 가는 증가 밖에 없다. (예외 처리)

라고 볼 수 있다. 0과 9는 예외처리, 연속 증감 X의 경우에는 변형 계단 수의 길이가 1일 경우를 제외하고는 존재하지 않으므로 전처리를 제외하곤 신경 쓰지 않아도 된다.

 

마지막 정답은 DP[N]의 모든 배열들을 더해주면 된다.

 

이 문제의 시간 복잡도는 O(구하고자 하는 변형 계단 수의 길이) == O(N)이다.

 

코드

---

#include <stdio.h>
#define mod 1000000007

int dp[101][10][5]; // 0 == 3 dec, 1 == 2 dec, 2(mid) == 1 dec || inc, 3 == 2 inc, 4 == 3 inc

int main(){
    int N;
    int sum = 0;
    int mid = 2;
    scanf("%d", &N);
    for (int i = 0; i < 10; i++){ // 길이가 1이고 증감 X의 변형 계단 수의 개수는 1개
        dp[1][i][mid] = 1;
    }
    for(int i = 1; i < 9; i++){ // 길이가 2일 경우에는 연속 1번 증/감 밖에 없음
        dp[2][i][mid+1] = dp[1][i-1][mid];
        dp[2][i][mid-1] = dp[1][i+1][mid];
    }
    dp[2][0][mid-1] = dp[1][1][mid]; // 0 예외처리
    dp[2][9][mid+1] = dp[1][8][mid]; // 9 예외처리
    for (int i = 3; i <= N; i++){
        for (int j = 0; j < 10; j++){
            if (j == 0){ // 0 예외처리 0일 경우는 1 -> 10으로 가는 감소 밖에 없다.
                dp[i][0][mid-1] = dp[i-1][1][mid+1] % mod;
                dp[i][0][mid-2] = dp[i-1][1][mid-1] % mod;
            }
            else if (j == 9) { // 9 예외처리 9일 경우는 8 -> 89로 가는 증가 밖에 없다.
                dp[i][9][mid+1] = dp[i-1][8][mid-1] % mod;
                dp[i][9][mid+2] = dp[i-1][8][mid+1] % mod;
            }
            else { // 점화식
                dp[i][j][mid+1] = (dp[i-1][j-1][mid-1] + dp[i-1][j-1][mid-2]) % mod;
                dp[i][j][mid+2] = dp[i-1][j-1][mid+1] % mod;
                dp[i][j][mid-1] = (dp[i-1][j+1][mid+1] + dp[i-1][j+1][mid+2]) % mod;
                dp[i][j][mid-2] = dp[i-1][j+1][mid-1] % mod;
            }
        }
    }
    for (int i = 0; i < 10; i++){ // 정답 N의 모든 배열을 더해준다.
        for (int j = 0; j < 5; j++){
            sum += dp[N][i][j];
            sum %= mod;
        }
    }
    printf("%d\n", sum % mod);
    
}

---