문제
풀이
전화기 키패드에서 인접한 버튼만 눌러 N자리 비밀번호를 만드는 경우의 수를 DP로 구한다.
- 키패드를 2D 배열로 모델링하고 상하좌우 인접 관계를 정의한다
dp[i][j]= i자리 비밀번호에서 마지막 숫자가 j인 경우의 수- 각 자릿수에서 인접한 버튼으로의 전이를 누적한다
핵심 아이디어: 키패드의 인접 관계를 그래프로 모델링하여 DP 전이를 정의한다.
코드
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
pad = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [0, -1, -1]]
MOD = 1234567
MAX = 1001
dp = [[0] * 10 for _ in range(MAX)]
for i in range(10):
dp[1][i] = 1
for i in range(1, MAX - 1):
for j in range(10):
if j == 0:
x, y = 0, 3
else:
x, y = (j - 1) % 3, (j - 1) // 3
for k in range(4):
ax, ay = x + dx[k], y + dy[k]
if -1 < ax < 3 and -1 < ay < 4 and pad[ay][ax] > -1:
dp[i + 1][pad[ay][ax]] = (dp[i + 1][pad[ay][ax]] + dp[i][j]) % MOD
T = int(input())
for _ in range(T):
n = int(input())
print(sum(dp[n]) % MOD)복잡도
- 시간: O(N²)
- 공간: O(N)