[백준] 계단 수 1562 - java

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

1562번: 계단 수

public class 계단수 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int dp[][][] = new int[N + 1][10][1 << 10];
		int MOD = 1000000000;
		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 < (1 << 10); k++) {
					if (j == 0) {
						dp[i][0][1 << 0 | k] = (dp[i][0][1 << 0 | k] + dp[i - 1][1][k]) % MOD;
					} else if (j == 9) {
						dp[i][9][1 << 9 | k] = (dp[i][9][1 << 9 | k] + dp[i - 1][8][k]) % MOD;
					} else {
						dp[i][j][1 << j | k] = (dp[i][j][1 << j | k] + dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k]) % MOD;
					}
				}
			}
		}

		int answer = 0;
		for (int i = 0; i < 10; i++) {
			answer = (answer + dp[N][i][(1 << 10) - 1]) % MOD;
		}
		System.out.println(answer);
	}
}

DP와 비트마스킹을 활용한 문제입니다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수라는 조건이 없다는 가정하에

2차원 배열로 나타낸다면

int dp[][] = new int[N+1][10];

 

  0    1      2     3      4     5      6     7      8      9

1    0  2  1  3  2  4  3  5  4  6  5  7  6  8  7  9   8

 

- N이 1일 때

dp[1][1~9] = 1

 

- N은 2이고 일의 자릿수가 1일때

dp[2][1] = dp[1][0] + dp[1][2]

N은 2일때 일의 자리가 1의 갯수는 이전 길이의 0의 갯수와 2의 갯수를 더한 값입니다.

 

여기서 0에서 9가 모두 등장하는 계단 수라는 조건을 추가한다면

각 길이마다 선택된 자릿수와 그 갯수를 기록해야합니다.

따라서 3차원 배열로

int dp[][][] = new int[N+1][10][1<<10];  // 총 10개의 값을 구분해야하므로

 

- N은 1일 때

dp[1][1~9][1<<(1~9)] = 1;

 

- N은 2이고 일의 자릿수가 1일 때

이전에 선택된 자릿수와 현재 선택된 자릿수를 합하여 모든 상태를 구해야합니다.

for(int k=0; k< 1<<10; k++){

      dp[2][1][1<<1 | k] = dp[2][1][1<<1 | k] + dp[1][0][k] + dp[1][2][k];

}

현재 1을 선택했으므로 1 << 1 | k 입니다.

 

이런식으로 순회를 하면되는데 정답을 1,000,000,000으로 나눈 나머지를 출력한다라는 조건이 있어

각 자릿수를 구할때마다 나머지연산을 해야합니다.