백준, 계단 수(1562, java)

문제 설명

길이가 N인 계단 수열의 수를 구하는 문제인데, 이때 0부터 9까지의 숫자가 모두 한 번 이상 등장해야 한다. 이때 0으로 시작하는 수는 계단수가 아니다.

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

1562번: 계단 수

문제 풀이

첫 번째 접근

DP 문제이기 때문에 처음에는 직접 손으로 풀어 써봤다.

이때 계단수의 규칙을 발견했는데, 0혹은 9의 옆 자리에는 1과 8밖에 오지 못한다는 점이다. 

일단 0의 경우에는 0과 x를 빼서 절댓값이 1이 되는 경우가 1혹은 -1인데, -1은 오지 못하니 1밖에 없다.

9 또한 10과 8이 있지만, 10은 고려 사항이 아니니 8밖에 오지 못하는 것이다.

 

나는 초반에 1차원 배열로 직전의 값만 이용해서 현재 값을 구하는 방식을 생각해봤지만, 제대로 된 규칙을 찾지 못해서 푸는 방법을 찾아봤다.

두 번째 접근

알아보니 해당 문제는 비트마스크로 푸는 것이었다.

 

참고한 블로그

https://loosie.tistory.com/171

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

일단 dp[n][k]를 n번째 위치에 k번째 숫자를 넣는 경우의 수라고 생각하자. 이때 0에서 9까지 숫자가 모두 적어도 한 번은 사용되어야 한다. 이 0부터 9까지 방문 표시를 비트마스크로 표현한다.

 

일단 dp[n][k]는 dp[n-1][k-1] + dp[n-1][k+1]로 n-1번째 위치에 k-1이 오는 경우 더하기 k+1이 오는 경우이다. 여기에 방문을 넣어주면 dp[n][k][visit | (1 << k)] = dp[n-1][k-1][visit] + dp[n-1][k+1][visit]이 된다.

 

여기서 visit | (1 << k)는 k를 방문했으므로 1을 왼쪽으로 k만큼 옮긴 값을 기존 visit 값에 or로 표시해주는 것이다. 예를 들어서 visit가 1011이고 k가 100이면 이 둘을 '|'로 연산하면 1111이 되는 것이다. 예시를 조금 더 풀어 써보자면 visit의 경우 0, 1, 3을 방문했고 k의 경우 2를 방문했다는 의미이다. 이 둘을 연산한 결과는 1111로 0, 1, 2, 3을 방문했다는 의미가 되는 것이다.

 

여기서 조심할 것은 k가 0일 때는 직전의 값이 1만 올 수 있으니 k+1만 더해주고 k가 9일 때는 직전의 값이 8만 올 수 있으니 k-1만 더해줘야 한다.

 

그리고 모든 계산 끝에 mod(1,000,000,000)로 나눠줄 것!

코드

java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //[n][k][visit], n번째의 위치에 k라는 수가올 때 visit에 있는 1만큼 방문함
        //visit 부분의 크기는 1을 왼쪽으로 10만큼 이동
        long[][][] dp = new long[101][10][1 << 10];
        int mod = 1000000000;
        long answer = 0;

        //초기 값
        //첫 번째 위치에 i라는 숫자가 올 때 i번째 숫자가 방문했다는 것을 표시
        for(int i=1; i<10; i++){
            dp[1][i][1<<i] = 1;
        }

        //dp[i][j][k | (1<<j)] = dp[i-1][j-1][k] + dp[i-1][j+1][k]
        for(int i=2; i<=n; i++){
            for(int j=0; j<10; j++){
                for(int k=0; k<(1 << 10); k++){
                    int visit = k|(1<<j);
                    if(j == 0){
                        //j가 0일 경우 양 옆에는 1밖에 못 온다.
                        dp[i][j][visit] += (dp[i-1][j+1][k]%mod);
                    }else if(j == 9){
                        //j가 9일 경우 양 옆에는 8밖에 못 온다.
                        dp[i][j][visit] += (dp[i-1][j-1][k]%mod);
                    }else{
                        dp[i][j][visit] += ((dp[i-1][j-1][k]%mod) + (dp[i-1][j+1][k]%mod));
                    }
                    dp[i][j][visit] %= mod;
                }
            }
        }

        for(int i=0; i<10; i++){
            answer += dp[n][i][(1 << 10) - 1]%mod;
            answer %= mod;
        }

        System.out.println(answer);


    }
}