출처
Koreatech OnlineJudge(링크)
문제이해
전화번호를 누를 때 연속된 각 번호가 상하좌우로 한 칸씩만 떨어져 있는 번호를 '걸기 쉬운 전화번호'라고 한다. 예를 들어 1236987412는 '걸기 쉬운 전화번호'이다.
999와 같이 같은 숫자가 연속하여 나오면 이에 해당하지 않는다.
길이가 N인 '걸기 쉬운 전화번호'를 구하는 문제이다.
문제접근
DP(동적 프로그래밍)로 해결할 수 있는 문제이다.
길이가 n이고, m으로 끝나는 '걸기 쉬운 전화번호'를 f(n, m)으로 정의한다.
그러면 길이가 n인 '걸기 쉬운 전화번호'의 개수는
이다.
그리고 길이가 n일 때의 경우의 수는 길이가 n-1일 때를 사용하여 구할 수 있다.
예를 들어, f(n, 2)는 f(n-1, 1) + f(n-1, 3) + f(n-1, 5)로 나타낼 수 있는데, 2와 인접해 있는 숫자가 1, 3, 5이기 때문이다.
다시 말하면 끝자리가 1이나 3, 또는 5인 전화번호 다음에만 2가 붙을 수 있다는 것이다.
이런 방법으로 0부터 9까지의 숫자에 대해 점화식을 세워 보면 다음과 같다.
f(n, 0) = f(n-1, 8)
f(n, 1) = f(n-1, 2) + f(n-1, 4)
f(n, 2) = f(n-1, 1) + f(n-1, 3) + f(n-1, 5)
f(n, 3) = f(n-1, 2) + f(n-1, 6)
f(n, 4) = f(n-1, 1) + f(n-1, 5) + f(n-1, 7)
f(n, 5) = f(n-1, 2) + f(n-1, 4) + f(n-1, 6) + f(n-1, 8)
f(n, 6) = f(n-1, 3) + f(n-1, 5) + f(n-1, 9)
f(n, 7) = f(n-1, 4) + f(n-1, 8)
f(n, 8) = f(n-1, 0) + f(n-1, 5) + f(n-1, 7) + f(n-1, 9)
f(n, 9) = f(n-1, 6) + f(n-1, 8)
bottom-up 방식으로 메모이제이션을 하면 답을 구할 수 있다.
구현
각 번호에 대해, 길이가 1일 때의 초기값은 1로 한다.
f(1, 0) = f(1, 1) = f(1, 2) = ... = f(1, 8) = f(1, 9) = 1
이기 때문이다. (이 경우에 답은 10이 된다.)
길이가 2일때 위 0~9에 대해 점화식을 한 번 시행하면 되고,
길이가 3일때는 두 번 시행하면 된다.
주의할 점은 mod 1,000,000,007을 연산해야 한다는 것인데,
점화식에서 최대 4개의 항을 더하므로 32비트 unsigned int이상의 자료형을 사용하면 편하게 구현할 수 있다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1057/1057.c