Posts 알고리즘 - 1240. [S/W 문제해결 응용] 단순 2진 암호코드
Post
Cancel

알고리즘 - 1240. [S/W 문제해결 응용] 단순 2진 암호코드

SW Expert Academy 의 1240번 - 단순 2진 암호코드 문제입니다.


  • 난이도 : 1~2

문제 조건

문제 해석에 조금 시간이 걸렸는데 알고 보니 어려운 내용은 크게 없었습니다.

예를 들어, 인풋 파일이 다음과 같이 주어졌을 경우

00000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000
01110110110001011101101100010110001000110100100110111011
01110110110001011101101100010110001000110100100110111011
01110110110001011101101100010110001000110100100110111011
01110110110001011101101100010110001000110100100110111011
00000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000

위에서 0과 1로 이루어진 문자열 한 줄만 읽어와서 처리하면 됩니다.

(0과 1로 이루어진 같은 숫자 배열들을 여러 줄 연이어 쓴 것은 바코드처럼 보이기 위함으로 추측되지만 그 이유는 정확히 알 수 없는 것 같습니다..)

문제를 자체 해석하여 다시 풀어 쓰자면..

  • 0부터 9까지의 숫자는 아래와 같이 각각

    0001101, 0011001, 0010011, 0111101, 0100011, 0110001, 0101111, 0111011, 0110111, 0001011 로 대신 표현됩니다.

    암호 코드는 총 8개의 숫자로 이루어져 있습니다. (즉, 8개 * 7개 binary = 56개의 숫자)

    인풋에서 읽어온 56개의 숫자를 위의 규칙에 따라 7개씩 끊어서 0~9 사이 자연수 8자리로 변환시킨 뒤, 정상적인 암호코드인지 판별해야 합니다.

  • 정상적인 암호코드 판별법

    읽어온 자연수 8자리에서 ‘(홀수 자리의 합) * 3 + 짝수 자릿수의 합’ 이 10의 배수면 올바른 암호코드입니다.


Input

  • 한 개의 테스트 케이스 당
    • 첫 줄에 두 개의 자연수 N(배열의 세로 크기), M(배열의 가로 크기)가 주어집니다.
    • 그 다음 N개의 줄에는 M개의 가로 크기를 가지는 배열의 값이 주어집니다.

Output

정상적인 암호코드 판별법 을 적용하여 올바른 암호코드라는 결과를 얻으면, 그 자연수 8자리의 모든 합을 구해 출력합니다.


생각한 아이디어

어차피 0부터 9까지의 수와 대응되는 7자리의 이진 숫자는, 맨 끝의 자리가 모두 1이고,
암호코드 자체는 처음부터 56자리의 숫자라고 정해져 있기 때문에

인풋값을 배열의 마지막 번째(즉, 인풋값의 한 행에서 M번째)부터 읽으면서 1을 만나면,
그 인덱스를 저장하고, 해당 위치부터 56개만큼 숫자를 읽고,
그 안에서는 7개씩 다시 구분해서 자연수로 변환해 저장하였습니다.

그리고 암호코드 판별법을 적용해서 맞으면 자릿수의 모든 합을 출력합니다.

개발 언어로 어디까지 구현할 수 있는지 그 실력을 판단하는 문제로 보입니다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <string.h>

char zero[8] = "0001101";
char one[8] = "0011001";
char two[8] = "0010011";
char three[8] = "0111101";
char four[8] = "0100011";
char five[8] = "0110001";
char six[8] = "0101111";
char seven[8] = "0111011";
char eight[8] = "0110111";
char nine[8] = "0001011";
int find(char* input, int idx);

int main() {

	int test_case=0;
	int N, M, flag = 0;
	int idx;
	int pResult, pIter;
	char temp_input[1000];
	char input[1000];
	int pass[8];
	int verify, allSum = 0;

	scanf("%d", &test_case);
	for (int i = 1; i <= test_case; i++) {

		scanf("%d %d", &N, &M);

		for (int j = 0; j < N; j++) {
			fgetc(stdin);
			fgets(temp_input, M, stdin);
			// 숫자 1을 찾기
			for (int n = M; n >= 0; n--) {
				if (temp_input[n] == '1' && flag == 0) {
					flag = 1;
					idx = n;
					strcpy(input, temp_input);
				}
			}
			fgetc(stdin);
		}

		pIter = 0;

		for (int m = 7; m >=0; m--) {
			pResult = find(input, idx-pIter);
			pass[m] = pResult;
			pIter += 7;
		}

		allSum = pass[0] + pass[1] + pass[2] + pass[3] + pass[4] + pass[5] + pass[6] + pass[7];
		verify = pass[0] + pass[2] + pass[4] + pass[6]; // 홀수자리의 합
		verify = verify * 3;
		verify = verify + pass[1] + pass[3] + pass[5] + pass[7];
		
		if (verify % 10 == 0)
		{
			printf("#%d %d\n", i, allSum);
		}
		else {
			printf("#%d 0\n", i);
		}
		flag = 0;
		
	}

}


int find(char* input, int idx) {
	char temp[8];
	int iter = 6;

	for (int i = idx; i >= idx - 6; i--)
		temp[iter--] = input[i];
	temp[7] = '\0';

	if (!strcmp(zero, temp))
		return 0;
	else if (!strcmp(one, temp))
		return 1;
	else if (!strcmp(two, temp))
		return 2;
	else if (!strcmp(three, temp))
		return 3;
	else if (!strcmp(four, temp))
		return 4;
	else if (!strcmp(five, temp))
		return 5;
	else if (!strcmp(six, temp))
		return 6;
	else if (!strcmp(seven, temp))
		return 7;
	else if (!strcmp(eight, temp))
		return 8;
	else if (!strcmp(nine, temp))
		return 9;
}

자료구조 - Tree의 개념과 용어

[백준] 2839번 - 설탕 배달