[JAVA] 백준 변형 계단수 18244 (다이나믹프로그래밍)

https://www.acmicpc.net/problem/18244

18244번: 변형 계단 수

 

"쉬운 계단수" 문제를 먼저 풀고 나면 좀 더 쉽게 접근 할 수 있습니다. 접근방법이 비슷하기 때문입니다.

https://onejunu.tistory.com/143?category=882099 

[JAVA] 백준 쉬운 계단 수 10844 (다이나믹 프로그래밍)

 

쉬운계단수 문제에 1가지 조건이 추가 되었습니다. 바로 3번연속 증가 또는 감소하면 안된다는 조건 입니다.

 

이전 조건에 대해서는 위 링크로 설명을 대체하고 나머지 1개의 조건에 대해서만 설명하겠습니다.

 

숫자의 마지막 부분만 연속적으로 증가 또는 감소 되었는지 체크하면 됩니다. 왜냐하면 숫자 중간에 증가 되었는지 감소되었는지는 이미 계산을 해오면서 3번연속 증가 또는 감소를 항상 체크해 왔기 때문에 중간부분은 고려대상이 아닙니다. 

 

이제 위 조건을 어떻게 일반화 하여 점화식을 세울 수 있는지 먼저 현재 상태를 정의해 봅시다.

현재 상태를 d 라고 합시다. d 를 아래처럼 정의합니다.

d = 증가 또는 감소를 체크 하는 변수

d == 0 : 증가 또는 감소가 없는 상태 (한자리 수인경우)
d == 1 : 1번 증가된 상태 
d == 2 : 2번 증가된 상태
d == 3 : 1번 감소된 상태
d == 4 : 2번 감소된 상태

 

그리고 디피에 사용할 배열의 인덱스가 어떤 의미로 사용될지 정의해봅니다.

 

dp[i][j][k]

i == 현재 숫자의 길이
j == 현재 숫자의 마지막 수
k == 마지막 수의 증가 감소 상태 (d로 정의한값)

예를 한번 들어보겠습니다.

 

1) dp[3][4][2] 로는 어떤 숫자를 가질 수 있을 까요? (2번 증가된 상태)

-> 정답 : 3234 , ...

 

2) dp[3][4][1] 로는 어떤 숫자를 가질 수 있을 까요? (1번 증가된 상태)

-> 정답:  2101 , ...

 

3) dp[3][4][0] 로는 어떤 숫자를 가질 수 있을 까요? (0번 증가된 상태)

-> 정답: 없음. 0번 증가된 상태는 한자리 수 외에 가질 수 없음

 

4) dp[3][4][3] 로는 어떤 숫자를 가질 수 있을 까요? (1번 감소된 상태)

-> 정답: 3454  , ...

 

5) dp[3][4][4] 로는 어떤 숫자를 가질 수 있을 까요? (2번 감소된 상태)

-> 정답 :  5654 ,...

 

이제 코드로 점화식을 한번 세워 보겠습니다.

 

/* 
i == 숫자의 길이
j == 마지막 숫자
*/

// 1감소된 상태 (d=3) 과 2감소된 상태 (d=4) 를 정의하기 
if(j < 9) {
  dp[i][j][3] = i-1 이고 j+1 이면서 d=0(증가X),d=1(1증가),d=2(2증가) 상태에서 올 수 있음.
  dp[i][j][4] = i-1 이고 j+1 이면서 d=3(1감소)상태에서만 올 수 있음.
}
// 1증가된 상태 (d=1) 과 2증가된 상태 (d=2) 를 정의하기 
if(j > 0) {
  dp[i][j][1] = i-1 이고 j-1 이면서 d=0(증가X),d=3(1감소),d=4(2감소) 상태에서 올 수 있음.
  dp[i][j][2] = i-1 이고 j-1  이면서 d=1(1증가)상태에서만 올 수 있음.
}

 

첫째항을 정의해보겠습니다.

 

// dp[i][j][d] = i = 길이 , j = 마지막수 , d = 0,1,2 -> 증가된 수 , 3,4 -> 감소된 수 체크
for(int i=0;i<10;i++) dp[1][i][0] = 1;

 

이제 정의된 식을 바탕으로 코드를 작성해보겠습니다.

 

for(int i=2;i<=n;i++) {
  for(int j=0;j<=9;j++) {
    if(j < 9) {
      dp[i][j][3] = dp[i][j][3] + dp[i-1][j+1][0]
      dp[i][j][3] = dp[i][j][3] + dp[i-1][j+1][1]
      dp[i][j][3] = dp[i][j][3] + dp[i-1][j+1][2]
      dp[i][j][4] = dp[i][j][4] + dp[i-1][j+1][3]
    }
    if(j > 0) {
      dp[i][j][1] = dp[i][j][1] + dp[i-1][j-1][4]
      dp[i][j][1] = dp[i][j][1] + dp[i-1][j-1][3]
      dp[i][j][1] = dp[i][j][1] + dp[i-1][j-1][0]
      dp[i][j][2] = dp[i][j][2] + dp[i-1][j-1][1]
    }
  }
}

 

이것또 역시 MOD로 나눠줘야 하기 때문에 MOD를 추가한 전체코드를 첨부하겠습니다.

 

package boj.P18244;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static Fs fs = new Fs();
    static int MOD = 1_000_000_007;
    static int[][][] dp = new int[101][10][5];
    public static void main(String[] args) throws Exception {
        int n = fs.nInt();

        // dp[i][j][k] = i = 길이 , j = 마지막수 , k = 0,1,2 -> 증가된 수 , 3,4 -> 감소된 수 체크
        for(int i=0;i<10;i++) dp[1][i][0] = 1;

        for(int i=2;i<=n;i++) {
            for(int j=0;j<=9;j++) {
                if(j < 9) {
                    dp[i][j][3] = (dp[i][j][3] + dp[i-1][j+1][0])%MOD;
                    dp[i][j][3] = (dp[i][j][3] + dp[i-1][j+1][1])%MOD;
                    dp[i][j][3] = (dp[i][j][3] + dp[i-1][j+1][2])%MOD;
                    dp[i][j][4] = (dp[i][j][4] + dp[i-1][j+1][3])%MOD;
                }
                if(j > 0) {
                    // 1개가 증가된 상태는 모든 감소된 상태에서 한개 증가시 가능함.
                    dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][4])%MOD;
                    dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][3])%MOD;
                    // 증가 상태에서 1개씩 증가
                    dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0])%MOD;
                    dp[i][j][2] = (dp[i][j][2] + dp[i-1][j-1][1])%MOD;
                }
            }
        }

        long sum = 0;
        for(int i=0;i<10;i++) {
            for(int j=0;j<5;j++) {
                sum = (sum + dp[n][i][j])%MOD;
            }
        }

        System.out.println(sum);
    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws Exception{
            if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }
    }
}