[다이나믹 프로그래밍] ★ 1562번 - 계단 수

[백준] 1562번 - 계단 수

(한줄평) 간단하다고 생각했지만 0부터 9까지 숫자가 모두 등장했는지 확인하기 위한 아이디어를 떠올리기 어려웠던 문제였다. 비트 마스킹을 이용한 DP 문제

유사 문제: 10844

https://hseungyeon.tistory.com/302

[다이나믹 프로그래밍] 10844번 - 쉬운 계단 수

 

인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 0으로 시작하는 수는 계단수가 아니다.

수의 길이 n이 주어질 때 0~9까지 숫자가 모두 등장하는 계단 수의 총 개수를 구하는 문제로 비트마스킹을 이용한 DP 문제였다. 여기서는 dp 테이블을 3차원, 2차원 리스트로 만들어서 푸는 방법 2개가 존재한다. 다만 2차원 리스트로 푸는 방법이 메모리, 시간 효율이 더 뛰어나므로 2번 풀이를 추천한다.

 

10844번에서는 dp테이블을 d[계단수 길이][마지막 숫자] 2차원 리스트로 만들었다. 마지막에 오는 숫자가 0인지, 9인지, 0/9가 아닌지 3가지 경우에 따라 점화식을 적용하여 계산하면 됐다.

하지만 이문제는 0~9까지 숫자를 모두 사용해야한다는 조건이 붙었다. 사용한 숫자를 어떻게 체크할지가 이 문제를 푸는 핵심이다. 현재까지 사용된 숫자를 체크하기위해 bitmask를 이용해 10진수로 변환한다.

---

(풀이1) dp 테이블을 3차원 배열로 생성

풀이 시간: 60분 이내

1) 문제 해결 아이디어

여기서는 dp 테이블을 d[계단수 길이][마지막 숫자][비트마스크값] 이렇게 3차원 리스트로 만들었다.

0~9까지 숫자 사용을 체크하기 위해 비트마스크를 이용했다.

 

일단 dp 테이블은 d[n][10][1024] 로 생성하고 0으로 초기화해주었다.

1) 계단수의 길이 범위: n(0~n)

2) 마지막 숫자에 올 수 있는 수의 범위: 10(0~9)

3) 가능한 비트 마스크 값 범위: 1024(0~1023)

 

Q. 비트 마스크 값의 범위가 0~1023인 이유는?

0~9까지 숫자 사용 여부를 0/1로 체크할 수 있다. 가능한 비트마스크 값은 2**10 = 1024개가 된다.

아래와 같이 사용된 숫자는 1로 바꾸고 그 값을 10진수로 변환한 값을 사용한다.

 

<비트 마스크 값 처리하기>

기존 계단 수 뒤에 추가할 값에 따라 비트 마스크 값을 계산해서 3차원 리스트에 값을 넣어주어야한다.

이렇게 만들어 주기 위해 OR 연산을 하면된다.

1) 추가할 값이 계단 수에 없는 값인 경우,

새로운 비트마스크 값 = 기존 비트 마스크 값 + 추가할 값

2) 추가할 값이 계단 수에 있는 값인 경우,

새로운 비트마스크 값 = 기존 비트 마스크 값

<경우의 수>

아래와 같이 마지막 숫자가 무엇이냐에 따라 3가지 경우로 나눌 수 있다.

다만, 코드를 더 간단하게 하기 위해 아래와 같이 2가지 경우를 모두 if문으로 검사하는 방식으로 바꿀 수도 있다.

 

<점화식>

[참고] https://chinpa.tistory.com/122

[백준] 1562 - 계단 수 (G1)

 

2) 소스코드

n = int(input())  # 계단 수 길이

# n * 10 * 1024
# [길이][마지막 숫자][비트마스크값]
d = [[[0] * 1024 for _ in range(10)] for _ in range(n)]

# 길이가 1일 때 초기화
# 0으로 시작하는 값은 계단수가 아니므로 1~9 까지만 1으로 초기화
for i in range(1, 10):
  # 비트 마스크 값
  d[0][i][1 << i] = 1

for len in range(n-1):
  for last in range(10):
    for bit in range(1024):
      # 1. 마지막 숫자가 9보다 작다면
      if last < 9:
        # 다음에 올 숫자가 아직 사용되지 않았으면 더해주기
        next_bit = bit | (1 << (last + 1))
        d[len+1][last+1][next_bit] += d[len][last][bit]
      # 2. 마지막 숫자가 0보다 크다면
      if last > 0:
        # 다음에 올 숫자가 아직 사용되지 않았으면 더해주기
        next_bit = bit | (1 << (last - 1))
        d[len+1][last-1][next_bit] += d[len][last][bit]
      '''
      # 1. 마지막 숫자가 0이면 다음에 올 수 있는 숫자는 1개
      if last == 0:
        # 새로 계산한 비트 마스크 값(원래 값과 추가할 값 or 연산)
        new_bit = bit | (1 << (last + 1))
        d[len + 1][last + 1][new_bit] += d[len][last][bit]
      # 2. 마지막 숫자가 9이면 다음에 올 수 있는 숫자는 1개
      elif last == 9:
        # 새로 계산한 비트 마스크 값(원래 값과 추가할 값 or 연산)
        new_bit = bit | (1 << (last - 1))
        d[len + 1][last - 1][new_bit] += d[len][last][bit]
      # 3. 마지막 숫자가 1~8이면 다음에 올 수 있는 숫자는 2개
      else:
        # 새로 계산한 비트 마스크 값(원래 값과 추가할 값 or 연산)
        new_bit = bit | (1 << (last - 1))
        d[len + 1][last - 1][new_bit] += d[len][last][bit]
        new_bit = bit | (1 << (last + 1))
        d[len + 1][last + 1][new_bit] += d[len][last][bit]
      '''
res = 0
# 계단수길이가 n, 모든 숫자를 사용했을 때
# 마지막 숫자가 0~9일때
for i in range(10):
  res += d[n-1][i][1023]
print(res % 10**9)

 

(풀이2) dp 테이블을 2차원 배열로 생성(추천!)

풀이 시간: 30분 이내

1) 문제 해결 아이디어

1번 풀이에서는 dp 테이블을 3차원 배열로 만들었지만 사실상 우리가 값을 계산할 때 리스트의 전체 값들을 활용하는 것이 아니라 d[현재 길이 - 1]인 리스트의 값만 알면 된다.

dp테이블을 d[10][1024] 크기로 생성하고 (계단수의 길이-1)만큼 반복문을 돌릴 때마다 계산한 값을 기록해 둘 2차원 리스트(tmp)를 tmp[10][1024]로 생성한다. 그리고 2가지 경우에 따라 계산한 값을 dp테이블이 아닌 tmp에 넣고 현재 계단수 길이에 대해 반복문을 모두 돌면 기록했던 값(tmp)를 dp테이블(d)에 업데이트한다.

 

2) 소스코드

n = int(input())  # 계단 수 길이

# 10 * 1024
# [마지막 숫자][비트마스크값]
d = [[0] * 1024 for _ in range(10)] 

# 길이가 1일 때 초기화
# 0으로 시작하는 값은 계단수가 아니므로 1~9 까지만 1으로 초기화
for i in range(1, 10):
  # 비트 마스크 값
  d[i][1 << i] = 1

for i in range(1, n):
  tmp = [[0] * 1024 for _ in range(10)]  # 계산한 값을 기록해둘 리스트
  for last in range(10):
    for bit in range(1024):
      # 1. 마지막 숫자가 9보다 작다면
      if last < 9:
        # 다음에 올 숫자가 아직 사용되지 않았으면 더해주기
        next_bit = bit | (1 << (last + 1))
        tmp[last+1][next_bit] += d[last][bit]
      # 2. 마지막 숫자가 0보다 크다면
      if last > 0:
        # 다음에 올 숫자가 아직 사용되지 않았으면 더해주기
        next_bit = bit | (1 << (last - 1))
        tmp[last-1][next_bit] += d[last][bit]
  # 기록한 값 업데이트
  d = tmp

res = 0
# 계단수길이가 n, 모든 숫자를 사용했을 때
# 마지막 숫자가 0~9일때
for i in range(10):
  res += d[i][1023]
print(res % 10**9)

 

[참고] https://hddcp.tistory.com/18

[백준] 1562 - 계단 수