[BOJ] 백준 1562번 계단 수 (Java)

#1562 계단 수 

난이도 : 골드 1

유형 : DP / 비트마스킹 

1562번: 계단 수

▸ 문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

▸ 입력

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

 

▸ 출력

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

 

 

 

 

문제 풀이

dp문제를 푸는데 0~9 숫자 중 사용한 숫자를 체크해줘야하는 문제가 나왔다.

처음에는 boolean으로 체크해줘야하나 하다가 시간초과가 뜨고 문제도 잘 굴러가지 않았다. 그래서 검색해 본 결과 '비트마스킹'을 사용해줘야 하는 문제였다. 어려워서 구글링으로 참고하고 공부하면서 풀이하였다.

 

비트마스킹에 대해 모른다면 공부하고 오는 것을 추천한다 (공부하러가기)

 

❐ 풀이 과정

i : i자리 숫자 , j 끝나는 숫자 , k 마킹된 숫자라고 하자.

   j=9, 10 0000 0000 (9로 끝나는 숫자)

      k =1, 10 0000 0001 (9로 끝나는 숫자, 0,9 사용)

      k =2, 10 0000 0010 (9로 끝나는 숫자, 1,9 사용)

      ...

      k = 9, 10 0000 1001 (9로 끝나는 숫자, 0,3,9 사용)

      ...

      k = 1023, 11 1111 1111 (9로 끝나는 숫자, 0~9 모두사용)

 

 

🧑‍🏫 이해가 쉽게 예시를 몇개 풀어보자

 

1) 2자리 숫자, 끝자리 숫자는 3, (2,3)이 포함된 수는? 

   > i=2, j=3, k = 12 (00 0000 1100) 

  > 답 : 23 , 1개

 

2) 3자리 숫자, 끝자리 숫자는 4, (2,3,4)이 포함된 수는? 

  > i=3, j=4, k= 28 (00 0001 1100)

  > 답: 234 , 1개

 

3) 2자리 숫자, 끝자리 숫자 3, (2,3,4)이 포함된 수는?

   > 이는 두 개의 dp값을 구해야 한다.

   > i=2, j=3, k = 12 (00 0000 1100) > 23

   > i=2, j=3, k= 24 (00 0001 1000) > 43 

   > 답 : 23,43  (dp[2][3][12] + dp[2][3][24] = 2개)

 

위의 방식을 이해했으면 점화식을 다음과 같이 설계할 수 있다.

 

int bit = k | (1<<j);  현재 상태 k에 j(0~9)값을 갖는 상태를 추가해준다.

     ex) k=6, j=8 > bit=14

      ☛ k=6 (0110), j=8(1000) 이면 bit = 14(1110)

      ☛ (1,2) → (1,2,3)로 새롭게 3 상태 On

 

dp[n][num][bit] += dp[n-1][num+1][bit] + dp[n-1][num-1][bit];

      ☛ 길이가 n-1이고 끝자리 수가 num라고 하면 이는 계단 수이기 때문에 (끝자리에 num+1이 들어올 경우) + (끝자리에 num-1이 들어올 경우)를 더해주면 된다.

 

j==0, j==9

      ☛  예외) 끝자리가 0이나 9인 경우, 새로운 숫자는 각 1,8밖에 오지 못한다. 

if(j==0) {
	dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j+1][k]) % MOD;
}else if(j==9) {
	dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j-1][k]) % MOD;
}

 

 

풀이 코드

// #1562 dp 계단수 
import java.util.Scanner;

public class NumberOfStair {

	static int MOD = 1_000_000_000; 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[][][] dp = new long[n+1][11][1<<10];

		// 1<<i : 0~9 비트마스킹
		for(int i=1; i<10; i++) {
			dp[1][i][1<<i] =1;
		}

		/**
		 *  i : i자리 숫자
		 *  j 끝나는 숫자 , k 마킹된 숫자 
			  ex) 	j=9, 10 0000 0000 
					
					k =1, 10 0000 0001
					...
					k = 9, 10 0000 1001 
					...
					k = 1023, 11 1111 1111
					
			i : 2, j : 3, k : 00 0001 1100 : 28 
			2자리 숫자 중 4로 끝나면서 234가 포함된 계단 수는?
			답 : 23,43  (dp[2][3][12] + dp[2][3][24] = 2개)
		 */

		for(int i=2; i<n+1; i++) {
			for(int j=0; j<10; j++) {
				for(int k=0; k<1024; k++) {
					int bit = k | (1 << j);
					if(j==0) {
						dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j+1][k]) % MOD;
					}
					else if(j==9) {
						dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j-1][k]) % MOD;
					}
					else {
						dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j+1][k]+ dp[i-1][j-1][k]) % MOD;
					}
				}
			}
		}

		long sum = 0;
		System.out.println(dp[2][3][28]);
		for(int i=0; i<10; i++) {
			System.out.print(dp[n][i][1023]+" ");
			sum = (sum + dp[n][i][1023]) % MOD;
		}
		System.out.println();
		System.out.println(sum);
	}




}