백준 2780번 (C++)

https://www.acmicpc.net/problem/2780

2780번: 비밀번호

1. 문제

 석원이는 자신의 현관문에 비밀번호 기계를 설치했다. 그 기계의 모양은 아래 그림과 같다.
 지나가던 석원이 친구 주희는 단순한 호기심에 저 비밀번호를 풀고 싶어한다. 이때 주희는 바닥에 떨어져 있는 힌트 종이를 줍게 된다. 이 종이에는 석원이가 비밀번호를 만들 때 사용했던 조건이 적혀 있다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다.
 석원이의 힌트 종이는 다음과 같다.
 1. 비밀번호의 길이는 N이다.
 2. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다.
 3. 비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다.
  (ex. 15 라는 비밀번호는 불가능하다. (1과 5는 인접하지 않는다. ) 하지만 1236이라는 비밀번호는 가능하다.)

석원이가 자신의 현관문에 설치한 비밀번호 기계

2. 입력 / 출력

 가. 입력

 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 비밀번호의 길이 N이 주어진다.( 1 <= N <= 1,000 )

• 테스트 케이스의 수 T
• 비밀번호의 길이 N (1≤N≤1,000)

 

 나. 출력

 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라.

• 각각의 테스트 케이스에 대해서 조건을 만족하는 비밀번호의 개수

 ※  비밀번호의 개수를 1,234,567로 나눈 나머지를 출력한다.

 

3. 알고리즘

• 키패드 모양을 고려해서 인접할 수 있는 숫자 배열을 먼저 생각한다.

• 07	12, 14	21, 23, 25	32, 36
  41, 45, 47	52, 54, 56, 58	63, 65, 69	70, 74, 78
  85, 87, 89	96, 98

  여기서 2차원 배열을 써야겠다는 생각이 들었다.
• 비밀번호의 n번째자리에 k라는 숫자가 오려면 비밀번호의 (n-1)번째 자리에 k와 인접할 수 있는 숫자 m, n, ··· 중 하나가 와야 한다. 그러므로 다음과 같이 생각할 수 있다.

  ex) array[2][2] = array[1][1] + array[1][3] + array[1][5]

 

4. 전체 코드

#include <stdio.h>

int main() {
	int i, j, T, N, sum=0;
	int array[1001][10];
	int array2[1];

	scanf_s("%d", &T);
	
	for (i = 0; i < 10; i++) {
		array[1][i] = 1;
	}
	
	
	for (i = 2; i < 1001; i++) {
		for (j = 0; j < 10; j++) {
			switch (j) {
			case 0:
				array[i][j] = array[i - 1][7];
				break;

			case 1:
				array[i][j] = array[i - 1][2] + array[i - 1][4];
				break;

			case 2:
				array[i][j] = array[i - 1][1] + array[i - 1][3] + array[i - 1][5];
				break;

			case 3:
				array[i][j] = array[i - 1][2] + array[i - 1][6];
				break;

			case 4:
				array[i][j] = array[i - 1][1] + array[i - 1][5] + array[i - 1][7];
				break;

			case 5:
				array[i][j] = array[i - 1][2] + array[i - 1][4] + array[i - 1][6] + array[i - 1][8];
				break;

			case 6:
				array[i][j] = array[i - 1][3] + array[i - 1][5] + array[i - 1][9];
				break;

			case 7:
				array[i][j] = array[i - 1][0] + array[i - 1][4] + array[i - 1][8];
				break;

			case 8:
				array[i][j] = array[i - 1][5] + array[i - 1][7] + array[i - 1][9];
				break;

			case 9:
				array[i][j] = array[i - 1][6] + array[i - 1][8];
				break;
			}
		}
	}
	

	for (i = 0; i < T; i++) {
		scanf_s("%d", &N);
		for (j = 0; j < 10; j++) {
			sum += array[N][j];
		}
		array2[i] = sum;
		sum = 0;
	}

	for (i = 0; i < T; i++) {
		printf("%d\n", array2[i] % 1234567);
	}
}

 

5. 코드 세부 설명

 가. 변수, 배열 설정

int main() {
	int i, j, T, N, sum=0;
	int array[1001][10];
	int array2[1];

	scanf_s("%d", &T);
	
	for (i = 0; i < 10; i++) {
		array[1][i] = 1; //array[1][0] ~ array[1][9]는 1가지이다.
	}
}

• i, j : 반복문을 사용하기 위한 변수
• T : 테스트 케이스의 개수
• N : 비밀번호의 길이 (1≤N≤1,000)
• sum : 조건을 만족하는 비밀번호의 개수 (처음에는 0으로 초기화 시킴.)
• array[1001][10] : 조건에 부합하는 숫자 조합을 계산하기 위한 배열
• array2[1] : N가지의 비밀번호 개수를 저장하기 위한 배열

 

 나. 계산하는 부분

for (i = 2; i < 1001; i++) {
	for (j = 0; j < 10; j++) {
		switch (j) {
		case 0:
			array[i][j] = array[i - 1][7];
			break;

		case 1:
			array[i][j] = array[i - 1][2] + array[i - 1][4];
			break;

		case 2:
			array[i][j] = array[i - 1][1] + array[i - 1][3] + array[i - 1][5];
			break;

		case 3:
			array[i][j] = array[i - 1][2] + array[i - 1][6];
			break;

		case 4:
			array[i][j] = array[i - 1][1] + array[i - 1][5] + array[i - 1][7];
			break;

		case 5:
			array[i][j] = array[i - 1][2] + array[i - 1][4] + array[i - 1][6] + array[i - 1][8];
			break;

		case 6:
			array[i][j] = array[i - 1][3] + array[i - 1][5] + array[i - 1][9];
			break;

		case 7:
			array[i][j] = array[i - 1][0] + array[i - 1][4] + array[i - 1][8];
			break;

		case 8:
			array[i][j] = array[i - 1][5] + array[i - 1][7] + array[i - 1][9];
			break;

		case 9:
			array[i][j] = array[i - 1][6] + array[i - 1][8];
			break;
		}
	}
}

 비밀번호의 n번째자리에 k라는 숫자가 오려면 비밀번호의 (n-1)번째 자리에 k와 인접할 수 있는 숫자 m, n, ··· 중 하나가 와야 한다.

for (i = 0; i < T; i++) {
	scanf_s("%d", &N);
	for (j = 0; j < 10; j++) {
		sum += array[N][j];
	}
	array2[i] = sum;
	sum = 0; //꼭 초기화해주어야 한다.
}

 비밀번호의 개수 sum을 구하고 array2에 저장한다. 여러 케이스를 계산하고 그 결과를 한꺼번에 출력하기 때문이다. sum을 array2에 저장하고 나서는 꼭 초기화 해줘야 한다. 그러지 않으면 다음 케이스의 값만 출력되지 않고 그 전 케이스의 값이 더해져서 출력된다.

 

 다. 결과 출력

for (i = 0; i < T; i++) {
	printf("%d\n", array2[i] % 1234567);
}

 array2값을 1,234,567로 나눈 나머지를 차례로 출력한다.

 

6. 에러

 컴파일 했을 때 오류가 없었는데 값을 입력하고 실행시키니까 디버그 에러가 발생하였다. C++를 제대로 공부하지는 않았어서 오류의 원인이 무엇인지 잘 모르겠다. 오류의 원인을 찾으면 글을 업데이트 할 것이다.