백준 1562번 - 계단 수

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

1562번: 계단 수

[풀이]

​

DP문제.

​

길이를 1부터 N까지 1씩 늘리면서 만들어진 계단 수의 맨 뒤에 숫자를 추가해주는 방법으로 경우의 수를 구해준다.

​

ex)

N=10일 때 계단 수는 9876543210 이다.

여기서 N=11인 계단수를 구할 때는 9876543210 의 맨 뒤 수인 0과 1 차이나는 1을 추가해준다.

그러면 98765432101 이라는 수가 만들어진다.

​

만들어져있는 계단 수의 앞 또는 중간에 수를 붙이려고 하면 머리도 복잡해지고 가장 중요한 문제는 만들어진 수의 중복이 발생하는 경우가 생긴다.

​

그래서 중복을 방지하고 순차적으로 모든 경우의 수를 만들기 위해서 가장 맨 뒤에 숫자를 추가해주는 방법을 사용한다.

​

그리고 이 문제에서 또 중요한 점은 0~9까지 모든 수를 사용한 계단 수를 만들어야 하기 때문에 수를 사용했는지 체크를 해야한다.

​

ex) 계단 수 = 0123432101

수	0	1	2	3	4	5	6	7	8	9
사용 여부	V	V	V	V	V

위의 예에서 계단 수는 0~4의 숫자만 사용하고 있다.

​

문제에서 원하는 조건을 만족하지 못하는 계단 수이다.

​

문제의 조건을 만족하기 위해서는 위의 표에서 0~9의 숫자가 모두 체크되야 한다.

​

여기서 체크를 할 때 배열을 사용하지 않고 비트마스킹을 사용했다.

 

​

모든 수를 체크했을 때는 1111111111 , 모든 수가 체크되있지 않을 때는 0000000000이다.

​

위의 예에서 0123432101 계단 수는 0~4의 숫자만 사용했기 때문에 비스마스킹으로 표현하면 0000011111이 된다.

​

어떤 하나의 수를 체크했다는 표시를 하고 싶을 때는 1 << N 을 사용한다.

​

<< 는 1을 왼쪽으로 N번 시프트 연산하는 기호이다.

​

예를 들어, 1 << 3 이라고 쓰게 된다면, 0000000001 에서 1을 왼쪽으로 3번 밀기 때문에 0000001000이 된다.

​

0000001000 은 이진수이기 때문에 10진수로 바꾸면 8이 된다.

​

이런식으로 0~9의 수를 10개의 비트로 표현하면 비트가 모두 켜졌을 때 1111111111(2) = 10000000000(2) - 1 = 1024 - 1 = 1023 이다.

​

결국 10진수 1024보다 작은 수들로 10개의 비트를 표현할 수 있게 된다.

​

1 << N 을 한 뒤에 원래 비트와 | (or) 연산을 하면 N번째 비트를 켜는 효과를 얻을 수 있다.

​

ex) 1000000000 | 1 << 2 ( 9번째 비트가 켜져있는 상태인데, 2번째 비트를 켜고 싶을 때)

==> 1000000100

 

​

비트마스킹을 쓰는 이유는 dp배열을 integer 3차원 배열로 나타낼 수 있기 때문이다.

​

DP[계단 수의 길이][계단 수의 가장 끝 수][0~9 숫자 체크여부]

​

이제 위의 DP배열을 이용해서 3중 for문을 돌리면 된다.

​

가장 끝 수가 0, 9 일때는 뒤에 올 수 있는 수가 한 가지밖에 없다는 점을 유의하자.

​

​

[소스코드]

import java.util.Scanner;

public class bj1562 {	//bj1562 계단 수
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int maxBit=1<<10;
		int mod=1000000000;
		int[][][] dp=new int[n+1][10][maxBit];
		for(int i=1;i<=9;i++) {
			dp[1][i][1<<i]=1;
		}
		for(int i=2;i<=n;i++) {
			for(int j=0;j<=9;j++) {
				for(int k=0;k<maxBit;k++) {
					if(j-1>=0&&dp[i-1][j-1][k]!=0) dp[i][j][k|1<<j]=(dp[i][j][k|1<<j]+dp[i-1][j-1][k])%mod;
					if(j+1<=9&&dp[i-1][j+1][k]!=0) dp[i][j][k|1<<j]=(dp[i][j][k|1<<j]+dp[i-1][j+1][k])%mod;
				}
			}
		}
		int answer=0;
		for(int i=0;i<=9;i++) {
			answer=(answer+dp[n][i][maxBit-1])%mod;
		}
		System.out.println(answer);
	}
}