이 문제에서는 숫자 모바일 키패드가 제공됩니다. 현재 버튼의 위, 아래, 오른쪽, 왼쪽 버튼만 누를 수 있으며 대각선 키는 허용되지 않습니다. 또한 키패드의 * 및 # 버튼을 누를 수도 없습니다.
숫자가 주어지면 키패드를 사용하여 주어진 규칙을 유지하면서 형성될 수 있는 주어진 숫자의 가능한 수를 찾아야 합니다.
입력 및 출력
Input: Digit count. Say 3 digit numbers. Output: Number of possible 3 digit numbers, that can be formed with the given conditions. Here the answer is 138.
알고리즘
getCount(n)
입력: 자릿수 n.
출력: 모바일 키패드에서 n자리 숫자를 입력하는 가능한 방법.
Begin if n <= 0, then return 0 if n = 1, then return 10 define two array row and col to move each direction from current key 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 1 to 9, do totalCount := totalCount + count[i, n] done return totalCount End
예시
#include <iostream> using namespace std; char keypad[4][3] = { {'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'} }; int getCount(int n) { if(keypad == NULL || n <= 0) return 0; if(n == 1) return 10; //1 digit number 0-9 int row[] = {0, 0, -1, 0, 1}; //for up and down the row will change int col[] = {0, -1, 0, 1, 0}; //for left and right column will change int count[10][n+1]; //store count for starting with i and length j int move=0, rowMove=0, colMove=0, num = 0; int nextNum=0, totalCount = 0; for (int i=0; i<=9; i++) { //for length 0 and 1 count[i][0] = 0; count[i][1] = 1 } for (int k=2; k<=n; k++) { //for digits 2 to n for (int i=0; i<4; i++ ) { //for Row wise for (int j=0; j<3; j++) { // for column wise if (keypad[i][j] != '*' && keypad[i][j] != '#') { //keys are not * and # num = keypad[i][j] - '0'; //find the number from the character count[num][k] = 0; for (move=0; move<5; move++) { rowMove = i + row[move]; //move using row moving matrix colMove = j + col[move]; //move using column moving matrix if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 && keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') { nextNum = keypad[rowMove][colMove] - '0'; //find next number count[num][k] += count[nextNum][k-1]; } } } } } } totalCount = 0; for (int i=0; i<=9; i++) //for the number starting with i 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