1. 백준 10844번 쉬운 계단 수

2. 백준 1562번 계단 수

둘 다 동적 프로그래밍에 관한 내용이다. 

2번은 1번 문제에 하나의 조건만 추가되었다.

"0~9까지 모든 수를 한번 이상 사용해야 한다는 것이다." (길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개?) 이 과정에서 비트 마스크가 사용된다.

1번 백준 10844번 쉬운 계단 수 문제

i번째 자리의 수를 결정하고

i+1번째 자리의 수를 결정하는 부분을 재귀 호출한다.

앞자리 수가 결정되었을 때,

가능한 현재 자리 수는 앞자리수 - 1, 앞자리수 + 1 두 가지이다.

현재 자리 수는 0부터 9 사이의 숫자여야 하기 때문에

앞자리 수가 0일 때는, 현재 가능한 수는 1(앞자리수+1)뿐이고

앞자리 수가 9일 때는, 현재 가능한 수는 8(앞자리수-1)뿐이다.

종료 조건은 남은 자릿수가 0일 때 1을 리턴한다. (개수)

static int 계단수(int 길이, int 앞자리) { 
  if (길이 <= 0) // 종료 조건
    return 1; 
    
  int 결과 = 0; 
  
  if (앞자리 - 1 >= 0) 
    결과 += 계단수(길이 - 1, 앞자리 - 1); 
    
  if (앞자리 + 1 <= 9) 
    결과 += 계단수(길이 - 1, 앞자리 + 1); 
    
  return 결과; 
} 

static int solution(int N) { 
  int 결과 = 0; 
  for (int i = 1; i <= 9; ++i) 
    결과 += 계단수(N - 1, i); 
  return 결과; 
}

이는 O(2^N)의 시간 복잡도가 발생하여 "동적 프로그래밍"으로 시간 효율성을 높여야 한다.

결과 배열[길이][앞자리]를 저장하는 배열을 만들었다.

static final int M = 1000000000; 
static long[][] 결과배열; // 동적프로그래밍을 사용하기 위한 저장소

static long 계단수(int 길이, int 앞자리) {
  if (길이 <= 0) 
    return 1; 
    
  if (결과배열[길이][앞자리] > 0) 
    return 결과배열[길이][앞자리]; 
    
  long 결과 = 0; 
  if (앞자리 - 1 >= 0) 
  	결과 = (결과 + 계단수(길이 - 1, 앞자리 - 1)) % M; 
  if (앞자리 + 1 <= 9) 
  결과 = (결과 + 계단수(길이 - 1, 앞자리 + 1)) % M; 
  
  return 결과배열[길이][앞자리] = 결과; 
} 

static long solution(int N) { 
  long 결과 = 0; 
  for (int i = 1; i <= 9; ++i) 
    결과 = (결과 + 계단수(N - 1, i)) % M; 
  return 결과; 
}

2번 1562번 계단 수

모든 수를 사용해야 한다고 한다. 

보통 방문 여부를 결정할 때는 boolean으로 visited 여부를 결정한다.

하지만 이 문제에선 "비트 마스크"로 visited 여부를 결정한다.

비트 마스크는

방문하지 않았으면 0, 방문하였으면 1로 나타낸다.

만약

숫자 3이 방문하였으면 0000001000으로 표현하고

이는 1<<3으로도 표현할 수도 있다.

즉, 숫자 n이 방문하였으면 1<<n 으로 나타낸다.

숫자 5와 7이 방문하였으면 0010100000

숫자 0, 2, 9가 방문하였으면 1000000101

식으로 표현한다.

어떤 숫자를 방문한 상태에서 n을 방문할 경우

(방문한 상태를 나타내는 비트) | (1<<n)로 나타낸다.

즉 숫자 0과 9를 방문한 상태 비트는 (1000000001)이고

이 상태에서 숫자 2를 방문할 경우 (1000000101)

1000000001 | (1<<2)로 표현할 수 있다.

0부터 9까지 모든 숫자를 방문했을 경우

1111111111로 표현할 수 있고 (1<<10)-1로도 표현한다.

(아래에선 111111111으로 표현하지 않고 (1<<10)-1 로 나타냈다.)

모든 숫자가 방문했는지 여부를 확인하는 배열을 하나 추가해준다.

위의 코드에서 2차원 배열이었던 결과 배열을 3차원으로 변경해준다.

종료 조건은 남은 자릿수가 없을 경우 (길이가 0보다 작을 경우) 모든 숫자를 사용했는지 비트 마스크로 비교하였다.

비트가 (1<<10)-1과 같을 경우 1을 리턴

다를 경우 모든 숫자를 사용하지 않았으므로 0을 리턴한다.

현재 자리 수를 결정하고 나서 

비트도 변경해준다.

bit = 비트 | 1<< (앞자리-1)

bit = 비트 | 1<< (앞자리+1)

	static final int M = 1000000000;
	static long[][][] 결과배열;

	static long 계단수(int 길이, int 앞자리, int 비트) {
		if (길이 <= 0)
			return 비트 == (1 << 10) - 1 ? 1 : 0;

		if (결과배열[길이][앞자리][비트] > 0)
			return 결과배열[길이][앞자리][비트];

		long 결과 = 0;
		if (앞자리 - 1 >= 0) {
			int bit = 비트 | (1 << (앞자리 - 1));
			결과 = (결과 + 계단수(길이 - 1, 앞자리 - 1, bit)) % M;
		}
		if (앞자리 + 1 <= 9) {
			int bit = 비트 | (1 << (앞자리 + 1));
			결과 = (결과 + 계단수(길이 - 1, 앞자리 + 1, bit)) % M;
		}

		return 결과배열[길이][앞자리][비트] = 결과;
	}

	static long solution(int N) {
		결과배열 = new long[N][10][1 << 10];

		long 결과 = 0;
		for (int i = 1; i <= 9; ++i) {
			결과 += (계단수(N - 1, i, 1 << i) % M);
			결과 %= M;
		}
		return 결과;
	}

전체 코드 확인 백준 1562번 문제