모바일 숫자 키패드 문제: 만들 수 있는 n자리 숫자 조합 개수 구하기

문제 소개

모바일 숫자 키패드가 하나 주어집니다. 현재 누른 버튼을 기준으로 상·하·좌·우에 인접한 키만 누를 수 있으며, 대각선 방향의 키는 누를 수 없습니다. 또한 키패드의 *과 # 버튼은 사용이 금지되어 있습니다.

자릿수가 주어졌을 때, 위 규칙을 모두 지키면서 키패드로 만들 수 있는 숫자의 총 개수를 구하는 것이 이 문제의 목표입니다.

키 이동 규칙 예시

1 → 1, 2, 4
5 → 5, 2, 4, 6, 8
0 → 0, 8
7 → 7, 4, 8 (*은 제외)

입력과 출력

입력:
자릿수. 예를 들어 3자리 숫자
출력:
주어진 조건을 만족하는 3자리 숫자의 개수. 정답은 138입니다.

풀이 알고리즘: 동적 계획법

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

count[i][j]: 숫자 i로 시작하는 j자리 숫자의 개수
j자리 숫자의 개수는, 현재 키와 그에 인접한 키(상·하·좌·우)에서 시작하는 (j-1)자리 숫자의 개수를 모두 더한 값

예를 들어 숫자 5로 시작하는 3자리 숫자의 개수는, 5·2·4·6·8 각각으로 시작하는 2자리 숫자의 개수를 합산하면 됩니다. 한 자리 숫자(n = 1)의 경우 0~9 모든 숫자가 가능하므로 정답은 10입니다.

의사코드 getCount(n)는 다음과 같습니다.

입력: 자릿수 n
출력: 모바일 키패드로 입력할 수 있는 n자리 숫자의 가짓수

Begin
    if n <= 0, then
        return 0
    if n = 1, then
        return 10

    // 상하좌우 이동을 위한 방향 배열 row, col 정의
    define two array row and col to move each direction from current key
    // 크기 (10 x n+1)의 count 테이블 정의
    define count table of size (10 x n+1)

    for i in range 0 to 9, do
        count[i, 0] := 0
        count[i, 1] := 1
    done

    for k in range 2 to n, do
        for i in range 0 to 3, do
            for j in range 0 to 2, do
                if key[i, j] ≠ * or #, then
                    num := key[i, j]
                    count[num, k] := 0
                    for all possible moves, do
                        rowMove := i + row[move]
                        colMove := j + col[move]
                        if rowMove in (0..3), colMove in (0..2), and key ≠ * or #, then
                            nextNum := key[rowMove, colMove]
                            count[num, k] := count[num, k] + count[nextNum, k-1]
                    done
            done
        done
    done

    totalCount := 0
    for i in range 0 to 9, do
        totalCount := totalCount + count[i, n]
    done

    return totalCount
End

시간 복잡도는 키패드 칸 수(최대 12)와 자릿수 n에 비례하여 약 O(12 × n)으로 매우 효율적입니다.

C++ 예제 코드

#include <iostream>
using namespace std;

char keypad[4][3] = {
    {'1','2','3'},
    {'4','5','6'},
    {'7','8','9'},
    {'*','0','#'}
};

int getCount(int n) {
    if(n <= 0)
        return 0;

    if(n == 1)
        return 10;              // 한 자리 숫자는 0~9 모두 가능

    int row[] = {0, 0, -1, 0, 1};   // 위·아래 이동 시 행(row) 변화
    int col[] = {0, -1, 0, 1, 0};   // 왼쪽·오른쪽 이동 시 열(column) 변화

    int count[10][n+1];             // count[i][j]: 숫자 i로 시작하는 j자리 숫자의 개수
    int move=0, rowMove=0, colMove=0, num = 0;
    int nextNum=0, totalCount = 0;

    for (int i=0; i<=9; i++) {      // 길이 0과 1에 대한 초기화
        count[i][0] = 0;
        count[i][1] = 1;
    }

    for (int k=2; k<=n; k++) {                 // 2자리부터 n자리까지
        for (int i=0; i<4; i++ ) {             // 행 기준 반복
            for (int j=0; j<3; j++) {          // 열 기준 반복
                if (keypad[i][j] != '*' && keypad[i][j] != '#') {  // *과 #은 제외
                    num = keypad[i][j] - '0';                     // 문자를 숫자로 변환
                    count[num][k] = 0;

                    for (move=0; move<5; move++) {
                        rowMove = i + row[move];                  // 행 이동 적용
                        colMove = j + col[move];                  // 열 이동 적용
                        if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 &&
                            keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') {
                            nextNum = keypad[rowMove][colMove] - '0';  // 다음 숫자 결정
                            count[num][k] += count[nextNum][k-1];
                        }
                    }
                }
            }
        }
    }

    totalCount = 0;
    for (int i=0; i<=9; i++)           // 숫자 i로 시작하는 n자리 숫자의 개수 합산
        totalCount += count[i][n];
    return totalCount;
}

int main() {
    int n;
    cout << "Number of digits: "; cin >> n;
    cout << "Possible Combinations: " << getCount(n);
}

실행 결과

Number of digits: 3
Possible Combinations: 138