c언어 1562번 계단 수 (백준)

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

#include <stdio.h>

int main(void) {
	int n, dp[10][10][1024]={}, ans = 0, M = 1e9;

	scanf("%d",&n);
	for(int i=1;i<10;i++) dp[0][i][1<<i]=1;
	
	n-=1;
	for(int i=0;i<n;i++) {
		for(int j=0;j<10;j++) {
			for(int k=0;k<1024;k++) {
				if(dp[i][j][k]) {
					if(j==0) {
						dp[i+1][1][k | 1<<1] += dp[i][j][k]; 
						dp[i+1][1][k | 1<<1] %= M;
					}
					else if(j==9) {
						dp[i+1][8][k | 1<<8] += dp[i][j][k]; 
						dp[i+1][8][k | 1<<8] %= M;
					}
					else {
						dp[i+1][j+1][k | 1<<j+1] += dp[i][j][k];
						dp[i+1][j-1][k | 1<<j-1] += dp[i][j][k];
						dp[i+1][j+1][k | 1<<j+1] %= M;
						dp[i+1][j-1][k | 1<<j-1] %= M;
					}
				}
			} 
		}
	}

	for(int i=0;i<10;i++) {
		ans += dp[n][i][1023];
		ans %= M;
	} printf("%d",ans);
	return 0;
}

 

풀이 : 비트필드를 이용한 다이나믹 프로그래밍

 

1. n과 dp 배열을 준비합니다.

1.1 0~9 가 포함되었는지를 기록하기위해 0~1023 까지의 비트필드를 준비합니다. 고로 [n 의 최댓값][10][1023] 입니다.

 

2. 숫자가 0이라면 다음 수는 반드시 1, 9는 8입니다. 나머지 수 x의 다음 수는 x+1, x-1 입니다. (다이나믹 프로그래밍)

- 여기서 비트필드를 이용합니다.

 

ex)
dp[0][9][1<<9] = 1      //9......

->

dp[1][8][1<<9 | 1<<8] += dp[0][9][1<<9]  //98.......


1<<9 | 1<<8  = 384
->

dp[2][7][384 || 1<<7] += dp[1][8][384]  //987......

dp[2][9][384 || 1<<9] += dp[1][8][384]  //989......

 

2.1 dp 초기값은 dp[0][0][i] = i<<1 입니다. dp[0][0][0] = 0 을 한 이유는, 문제에서 계단 수는 0으로 시작하지 않기 때문입니다.

 

 

3. 다이나믹 프로그래밍을 반복문을 이용해 구현합니다. 단 overflow을 막기위해서 더한 다음, % 1000000000 을 해줍니다.

 

4. 계단수는 [n-1][x][1023]  (x는 0~9) 의 합 입니다.

단 이때도 overflow 을 방지해야합니다.