백준 - 계단의 수(1562)

정민주·2025년 9월 25일

코테

목록 보기

72/77

오늘 풀어볼 문제는 ⭐계단의 수 라는 문제이다.

1. 문제요약

45656-> 인접한 모든 자리 차이가 1임 -> 이런 걸 "계단 수" 라고 한다.
[계단 수 조건]
- 길이가 N이어야 함
- 0부터 9까지 숫자가 모두 등장해아 함
- 0으로 시작한다면 계단 수 X

2. 입출력

2.1 입력

N (1<=N<=100) 즉, 최대 수 10억

3. 알고리즘

일단 꿀팁이 하나 있다. 0~9 중에 어떤 수가 사용되었는지 저장하는 가장 효율적인 방법은 비트마스킹이란 것이다.

그 전에 비트의 연산법 부터 알아보자.

3.1 비트 연산법

일단 비트는 0(false)와 1(true)로 표현되는 가장 작은 단위이다.

이런 비트를 연산하는 방법에는 2가지가 있다.

1. 비트연산

AND OR XOR NOR
0&0=00|0=00^0=0~0=1
0&1=00|1=10^1=1~1=0
1&1=11|1=11^1=0

2. shift 연산

LEFT SHIFT : 기존값 * (2^N)
9(00001001)<<1 = 18(00010010)
3(00000011)<<3 = 24(00011000)

RIGHT SHIFT : 기존값 / (2^N)
13(00001101)>>1 = 6(00000110)
9(00001001)>>2 = 2(00000010)

4. 문제풀이

해당 문제를 풀기 위해선 3차원 배열과 비트마스킹 기법이 필요하다.

dp[i][j][k] : i 번째 숫자는 j이다. 현재까지 방문된 0~9까지의 기록은 k와 같다.

i의 범위는 입력값으로 주어지는 N과 범위가 동일하다.
j의 범위는 0~9이다.
k는 10개의 비트로 0~9의 방문처리를 하는 것을 말한다. 예를 들어, 0100000100(10진수 132)은 8과 2을 방문한 상태이다.
문제 조건 중, 0이 먼저 오는 경우는 발생해선 안되기에, dp[1][j][1<<j]=1로 초기화 시킨다. j는 0을 제외한 1부터 9까지 인덱스만 초기화한다.
모든 비트 연산이 끝난 후, dp[N][x][1024]의 모든 값을 더하면 된다. x는 당연히 0~9까지 범위 전체이다.

5. 코드

2가지 정도의 핵심 코드가 있다.

첫 번째는 현재 방문처리를 하는 코드이고, 두 번째는 dp 배열의 전개식이다.

변수명은 위에서 설명한 i, j, k가 아닌 명확한 order, orderNum, history로 사용한다.

5.1 현재 방문처리

for(int orderNum = 0; orderNum<=9; orderNum++){
  for(int history = 0; history<(1<<10); history++) {
    int currH = history | (1<<orderNum);
    ...
   }
 }

현재 hitory는 아무것도 방문하지 않은 상태 0000000000에서 0~9까지 모두 방문한 상태 1111111111 의 상태를 모두 순환한다.

그러나 상위 for문에는 현재 방문해야 하는 숫자인 orderNum 역시 0~9의 범위로 돌고 있다.

history는 이 orderNum의 방문여부를 포함하지 않기 때문에, 무조건 orderNum의 자리 bit는 1이 될 수 있게 해줘야 하는 것이 첫 번째 핵심코드이다.

5.2 dp 전개식

계단수의 특징은 양옆이 +-1씩 차이난다는 것이다. 그러나 양 쪽 끝인 0과 9는, 무조건 옆 자리 비트 하나만으로 계산을 해야한다.

이 점을 생각하고 아래와 같은 코드를 짜면 된다.

if(orderNum == 0) dp[order][orderNum][currH] += dp[order-1][orderNum+1][history]%MOD;

else if(orderNum==9) dp[order][orderNum][currH] += dp[order-1][orderNum-1][history]%MOD;

else dp[order][orderNum][currH] += 
	(dp[order-1][orderNum-1][history]%MOD) + (dp[order-1][orderNum+1][history]%MOD);

5.3 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
   static int dp [][][];
   static int N;
   static final int MOD = 1000000000;

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       N = Integer.parseInt(br.readLine());

       dp = new int[N+1][10][1<<10]; //[order][orderNum][history]

       //숫자의 첫 번째 자릿수가 0이 되지 않도록 초기화.
       for(int orderNum = 1; orderNum<=9; orderNum++) dp[1][orderNum][1<<orderNum] = 1;

       //숫자의 두 번째 자릿수부터 계산 시작
       for(int order=2; order<=N; order++){
           for(int orderNum = 0; orderNum<=9; orderNum++){
               for(int history = 0; history<(1<<10); history++) {
                   int currH = history | (1<<orderNum);
                   if(orderNum == 0) dp[order][orderNum][currH] += dp[order-1][orderNum+1][history]%MOD;
                   else if(orderNum==9) dp[order][orderNum][currH] += dp[order-1][orderNum-1][history]%MOD;
                   else dp[order][orderNum][currH] += (dp[order-1][orderNum-1][history]%MOD+dp[order-1][orderNum+1][history]%MOD);

                   dp[order][orderNum][currH]%=MOD;
               }
           }
       }

       long ans = 0;

       for(int orderNum=0; orderNum<=9; orderNum++){
           ans+=dp[N][orderNum][1024-1] %MOD;
           ans%=MOD;
       }

       System.out.println(ans);


   }
}

정민주