📌 문제 : 백준 1562번
📌 문제 탐색하기
N : 자연수 ($ 1 ≤ N ≤ 100$)
문제 풀이
길이가 N이면서 0~9 사이 모든 수가 등장하는 계단 수의 개수를 구하는 문제이다.
그 개수를 1,000,000,000으로 나눈 나머지를 출력해야 한다.
⭐️ 계단 수 조건
- 인접한 모든 자리의 차이가 1인 수
- 0으로 시작하는 수는 계단 수 ❌
‼️ 고려해야 할 점
- 원하는 자리의 계단 수를 구하기 위해선 이전 자리의 계단 수들 정보가 필요하다.
→ 점화식을 세워 다이나믹 프로그래밍 알고리즘을 활용할 수 있다. - 조건으로 해당 수에 0~9까지의 수가 모두 등장해야 하므로 이를 확인하는 단계를 추가해야 한다.
→ 비트 마스킹 기법을 활용해 0부터 9까지의 숫자 사용 여부를 파악한다.
위의 내용을 고려해 dp를 구현한다.
1️⃣ DP 테이블 만들기
- 구하려는 자리의 위치, 지금 자리에 들어갈 숫자, 사용 여부 판단을 위한 비트 마스크 3가지의 상태 저장 필요
→ 3차원의 DP 테이블 정의:dp[위치][숫자][비트마스크] - 1자리의 숫자이면서 숫자가 1~9인 경우의 수는 각각 1
→dp[1][1부터 9까지][비트마스크] = 1로 초기화
2️⃣ DP 테이블 채우기
- 점화식
- 길이가 i이면서 현재 숫자가 j인 계단 수는 이전 계단 수로부터 얻을 수 있음
- 숫자가 0 → 더 큰 수 고려
- 숫자가 9 → 더 작은 수 고려
- 나머지 → 양쪽 모두 고려
- 비트 마스크
- 총 10자리의 수 확인 → 개의 비트 마스크 사용
- 0부터 9까지의 숫자가 있는지 확인해야 하므로 조건문 추가
x사용 여부 표시 방법 :mask | (1 << x)
- 3차원이므로 3중 for문 사용
- 1 : 1 제외 2부터 N까지 자릿수 하나하나 접근
- 2 : 0부터 9까지의 숫자 접근
- 3 : 비트마스크 하나하나 접근
3️⃣ 결과 얻기
- N자리에서 0~9까지 숫자를 모두 다 사용한 경우들을 합한다.
가능한 시간복잡도
dp 테이블 채우기 →
최종 시간복잡도
N이 최대 100이므로 제한 시간 2초 내에 연산이 가능하다.
알고리즘 선택
다이나믹 프로그래밍과 비트 마스킹 활용
📌 코드 설계하기
- N 입력
- dp 테이블 정의
- dp 테이블 초기화
- dp 테이블 채우기
- 결과 계산
- 결과 출력
📌 시도 회차 수정 사항
다회차
- 너무 어려워서 모든 과정을 하나씩 찾아가면서 풀었다.
📌 정답 코드
import sys
input = sys.stdin.readline
# N 입력
N = int(input())
# dp 테이블 정의
dp = [[[0 for _ in range(1024)] for _ in range(10)] for _ in range(N+1)]
# dp 테이블 초기화
for i in range(1, 10):
dp[1][i][1 << i] = 1
# dp 테이븛 채우기
for n in range(2, N+1):
for i in range(10):
for bit in range(1024):
if i == 0:
dp[n][i][bit | (1 << i)] = (dp[n][i][bit | (1 << i)] + dp[n-1][i+1][bit]) % 1000000000
elif i == 9:
dp[n][i][bit | (1 << i)] = (dp[n][i][bit | (1 << i)] + dp[n-1][i-1][bit]) % 1000000000
else:
dp[n][i][bit | (1 << i)] = (dp[n][i][bit | (1 << i)] + dp[n-1][i+1][bit] + dp[n - 1][i - 1][bit]) % 1000000000
# 결과 계산
answer = sum(dp[N][j][1023] for j in range(10)) % 1000000000
# 결과 출력
print(answer)- 결과
