1240. [S/W 문제해결 응용] 1일차 - 단순 2진 암호코드
문제 접근
문제가 굉장히 복잡하다. 하지만 문제만 제대로 이해한다면 그렇게 어려운 문제는 아니었다.
문제를 다시 설명해주자면 8자리의 암호문이 있다. 암호문이 올바른 암호문인가를 알기 위해서는 이 8자리 암호문의 (홀수자리의 합)x3+짝수자리의 합이 10의 배수인지를 보면된다.
근데 이 8자리의 암호문은 총 56비트의 암호문으로 주어지는데 각 1자리가 7비트로 이뤄져있는셈이다. 7비트가 어떻게 이뤄져야 숫자가 나오는지는 문제에 나와있다.
이제 입력을 보면 2차원배열의 가로세로길이가 주어진다.
그 아래에 2차원배열이 주어지는데, 우리가 필요한 암호문 56비트는 이 안에 숨어있다. 암호문과 관련없는 부분들은 모두 0으로 처리되어있다.
따라서 우리는 2차원배열에서, 56비트의 암호문을 찾고, 각 7자리를 복호화하여 총 8자리의 암호문을 얻어서, 이 암호문이 올바른 암호문이라면 암호문의 각 자리의 합을 구하면 되고, 아니라면 0을 출력하면 되는 문제이다.
따라서 순서를 나눠보면
- 56비트의 암호문 찾기
- 각 7자리를 복호화하여 총 8자리의 암호문 저장하기
- 암호문이 올바른지 확인하기
가 되겠다.
문제 풀이
56비트의 암호문 찾기
56비트의 암호문을 편하게 찾으려면 규칙을 파악해야한다. 모든 숫자들의 비트환산값의 공통점을 찾아보면 무조건 마지막에 1로 끝나는 것을 확인할 수 있다. 따라서 뒤에서부터 하나씩 찾아보며 1일 경우 그 앞의 56자리가 56비트의 암호문이 된다. 이를 저장하면 된다.
sentence = deque() # 암호화된 56자리 비트를 저장할 리스트
for i in range(N):
for j in range(M-1,-1,-1): # 뒤에서부터 1인값을 찾는다. 모든 56자리비트 암호문은 마지막에 1로 끝나기때문에
if pan[i][j]=='1':
for k in range(j,j-56,-1):
sentence.appendleft(pan[i][k])
break
if len(sentence)!=0: # 이미 찾았으면 break
break각 7자리를 복호화하여 총 8자리의 암호문 저장하기
string_ex에는 총 10개의 7자리비트수가 들어가 있다. 각각의 인덱스가 비트를 복호화했을 때의 값이다.
이제 56자리의 리스트에서 7자리마다 끊어서 각 string_ex에 해당하는 값의 인덱스를 decode에 추가한다. 이렇게 되면 decode에는 비트복호화한 8자리의 암호문이 담길 것이다.
string = '' #7자리비트 저장할 변수
string_ex = ['0001101', '0011001', '0010011','0111101', '0100011', '0110001', '0101111','0111011','0110111','0001011'] # 암호문 리스트
decode = [] # 복호화한 값 들어갈 리스트
for i in range(1, 57):
string += sentence[i-1] #7자리까지
if i%7==0: # 7자리마다
for j in range(10):
if string == string_ex[j]: # 암호문에 해당하는 값이 있는지 확인
decode.append(j) # decode리스트에 복호화한 값 append
break
string='' # 7자리 체크 끝났기 때문에 다시 초기화암호문이 올바른지 확인하기
이제 암호문이 올바른지를 확인해야한다.
아래와 같이 단순하게 연산을 통해서 암호문이 올바른지 확인할 수 있다.
result = 0 # 짝수자리 값 더할 변수 및 최종 합 저장할 변수
result_odd = 0 # 홀수자리 값 더할 변수
for i, val in enumerate(decode):
if i%2==0: #홀수자리이면
result_odd+=val
else: #짝수자리이면
result+=val
result = result+(result_odd*3) # 홀수자리만 3곱하고 더하기
if result%10==0: #올바른 암호문이라면
print(f'#{test_case} {sum(decode)}')
else: # 올바리지 않은 암호문이라면
print(f'#{test_case} 0')제출 코드
from collections import deque
T = int(input())
for test_case in range(1, T + 1):
N, M = map(int, input().split())
pan = []
for i in range(N):
line = input().strip()
pan.append(line) #입력받기
sentence = deque() # 암호화된 56자리 비트를 저장할 리스트
for i in range(N):
for j in range(M-1,-1,-1): # 뒤에서부터 1인값을 찾는다. 모든 56자리비트 암호문은 마지막에 1로 끝나기때문에
if pan[i][j]=='1':
for k in range(j,j-56,-1):
sentence.appendleft(pan[i][k])
break
if len(sentence)!=0: # 이미 찾았으면 break
break
string = '' #7자리비트 저장할 변수
string_ex = ['0001101', '0011001', '0010011','0111101', '0100011', '0110001', '0101111','0111011','0110111','0001011'] # 암호문 리스트
decode = [] # 복호화한 값 들어갈 리스트
for i in range(1, 57):
string += sentence[i-1] #7자리까지
if i%7==0: # 7자리마다
for j in range(10):
if string == string_ex[j]: # 암호문에 해당하는 값이 있는지 확인
decode.append(j) # decode리스트에 복호화한 값 append
break
string='' # 7자리 체크 끝났기 때문에 다시 초기화
result = 0 # 짝수자리 값 더할 변수 및 최종 합 저장할 변수
result_odd = 0 # 홀수자리 값 더할 변수
for i, val in enumerate(decode):
if i%2==0: #홀수자리이면
result_odd+=val
else: #짝수자리이면
result+=val
result = result+(result_odd*3) # 홀수자리만 3곱하고 더하기
if result%10==0: #올바른 암호문이라면
print(f'#{test_case} {sum(decode)}')
else: # 올바리지 않은 암호문이라면
print(f'#{test_case} 0')