[백준 - 18244번] 변형 계단 수 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,007으로 나눈 나머지를 출력한다.

풀이

변형 계단 수가 총 몇 개인지 출력해야 한다.

각 자리 수마다 증가하거나 감소할 수 있기 때문에 완전 탐색으로 풀면 약 O(2^98)으로 불가능하다.

그래서 중복된 값이 있는지 찾아보고 있다면 dp를 활용해야 한다.
? ? ? 5 - - -

여기서 5의 상태는

• 4번째 자리에 있고,
• 첫 번째로 감소하고 있다

그래서 다음과 같은 경우

• 4 5 6 5 - - - (증가, 증가, 감소)
• 6 5 6 5 - - -(감소, 증가, 감소)
  ...

이후에 탐색은 완전히 동일한 탐색으로 진행된다. 그래서 값을 저장해놓고 중복 탐색을 방지할 수 있다. (dp 활용)

그러면 총 경우의 수는 (증가, 감소) (몇 번째 증가, 감소 인지) (몇 번째 자리인지) (어떤 수인지) 로 2 2 100 10이 되고,

dp[A][B][C][D]를 다음과 같이 정의하고 구현하면 된다.

• A -> (증가, 감소)
• B -> (몇 번째 증가, 감소 인지)
• C -> (몇 번째 자리인지)
• D -> (어떤 수인지)

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static final int inDe[] = {1, -1}; //증가, 감소
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      
      int[][][][] dp = new int[2][3][101][10]; //[A][B][C][D] -> A는 감소,증가, B는 몇 번째 증가 인지, C는 몇 번째 자리인지, D는 어떤 수인지
      init(dp); //-1은 방문하지 않음을 의미
      
      int answer = 0;
      if(N == 1) {
          System.out.println(10);
          return;
      }
      for(int i=0; i<=9; i++) {
          for(int j=0; j<=1; j++) {
              //증가 or 감소
              answer = (answer + find(j, 1, 2, i + inDe[j], dp)) % MOD;
          }
      }
      System.out.println(answer);
  }
  
  static int find(int A, int B, int C, int D, int[][][][] dp) {
      //[A][B][C][D] -> A는 감소,증가, B는 몇 번째 증가 인지, C는 몇 번째 자리인지, D는 어떤 수인지
      if(D < 0 || 9 < D) {
          //D는 0부터 9 사이의 수임
          return 0;
      }
      
      if(3 <= B) {
          //증가, 감소가 연속 3번 이상인 경우 탐색 x
          return 0;
      }
      
      if(C == N) {
          return 1;
      }
      
      if(dp[A][B][C][D] != -1) {
          //이미 방문을 했다면
          return dp[A][B][C][D];
      }
      
      int v = 0;
      for(int i=0; i<=1; i++) {
          //증가 or 감소
          int nextB = B + 1;
          if(A == 0 && i == 1) {
              //현재 증가 중인데 감소하는 경우
              nextB = 1;
          }
          if(A == 1 && i == 0) {
              //현재 감소 중인데 증가하는 경우
              nextB = 1;
          }
          v = (v + find(i, nextB, C + 1, D + inDe[i], dp)) % MOD;
      }
      
      dp[A][B][C][D] = v;
      return dp[A][B][C][D];
      
  }
  
  static void init(int[][][][] arr) {
      for(int i=0; i<arr.length; i++) {
          for(int j=0; j<arr[i].length; j++) {
              for(int k=0; k<arr[i][j].length; k++) {
                  for(int l=0; l<arr[i][j][k].length; l++) {
                      arr[i][j][k][l] = -1;
                  }
              }
          }
      }
  }
}