BOJ 7008 Double Trouble

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/7008
번역

문제
#

Alice Catherine Morris와 그녀의 여동생 Irene Barbara는 자주 이메일을 주고받습니다. 항상 도청을 경계하며 통신 내용을 비밀로 유지하고자, 그들은 메시지를 두 단계로 암호화합니다. 모든 비알파벳 문자를 제거하고 모든 문자를 대문자로 변환한 후:

각 문자를 알파벳에서 s 위치 뒤의 문자로 치환합니다 (1 <= s <= 25) - 이를 s만큼의 시프트라고 합니다.
단계 1의 결과를 m개의 문자로 된 그룹으로 나누고 각 그룹의 문자들을 역순으로 배열합니다 (5 <= m <= 20). 메시지의 길이가 m으로 나누어떨어지지 않으면, 마지막 k개(m보다 작은)의 문자들을 역순으로 배열합니다.

예를 들어, s = 2이고 m = 6이라고 가정합시다. 평문이 “Meet me in St. Louis, Louis.“라면, 불필요한 문자를 제거하고 대문자로 변경하면:

MEETMEINSTLOUISLOUIS

이것을 수정된 평문이라고 부릅니다. 그런 다음 각 문자를 2만큼 시프트합니다(여기서 Y는 A로, Z는 B로 치환됨):

OGGVOGKPUVNQWKUNQWKU

마지막으로 6개 문자로 된 각 그룹을 역순으로 배열합니다:

GOVGGOQNVUPKWQNUKWUK

마지막 두 문자가 마지막 역순 그룹을 구성했음에 주목하세요. 관례대로, 결과를 5개 문자 단위로 작성합니다. 따라서 암호문은:

GOVGG OQNVU PKWQN UKWUK

아쉽게도, 암호문이 도청되었을 때 s와 m의 값을 찾는 것은 그리 어렵지 않습니다. 사실 수정된 평문에 있는 단어인 크립(crib)을 알고 있다면 훨씬 더 쉽습니다. 위의 예에서 LOUIS가 크립이 됩니다. 여기서 여러분의 임무는 암호문과 크립이 주어졌을 때 s와 m을 찾는 것입니다.

입력
#

입력은 여러 문제 인스턴스로 구성됩니다. 입력의 첫 번째 줄에는 문제 인스턴스의 개수를 나타내는 양의 정수가 포함됩니다. 각 문제의 입력은 여러 줄로 구성됩니다. 문제의 첫 번째 입력 줄에는 암호문의 문자 개수와 같은 정수 n (20 <= n <= 500)이 포함됩니다. 다음 줄들에는 암호문이 포함되며, 모두 대문자로 5개 문자 단위로 묶여 하나의 공백으로 구분됩니다. (마지막 문자 그룹은 5개 미만의 문자를 포함할 수 있습니다.) 한 줄에 10개의 문자 그룹이 있으며, 마지막 암호문 줄만 예외일 수 있습니다. 암호문의 마지막 줄 다음 입력 줄에는 크립이 포함됩니다; 4개에서 10개(포함) 사이의 대문자로 구성된 단일 단어입니다.

출력
#

한 줄에 두 개의 정수 s와 m을 하나의 공백으로 구분하여 출력합니다. 이는 크립을 생성하는 암호화 키를 나타내며, s는 시프트이고 m은 역순 그룹 크기입니다. 해가 여러 개 있으면 가장 작은 s를 가진 것을 출력합니다. 같은 s를 가진 것이 여러 개 있으면 가장 작은 m을 가진 것을 출력합니다. 그러한 s와 m이 존재하지 않으면 “Crib is not encrypted.“라는 메시지를 출력합니다.

🧐 관찰 및 접근
#

주어진 문장에서 (문제에서는 알파벳만 5개 단위로 쪼개져서 들어오긴 하지만) 비알파벳 문자를 모두 없애고, $s$만큼의 쉬프트와 $m$만큼의 뒤집기 연산을 수행해서 암호화하자.
이때, 문자열의 길이는 최대 $500$이고, 연산은 $O(N)$이 걸린다.
$s \leq 25$이고, $m \leq N$일 것이다. ($N+1$개 이상 뒤집는건 $N$개 뒤집는것과 같다.)
따라서 브루트포스로 시간복잡도 $O(N^2s)$ 정도에 수행 가능해보인다.

💻 풀이
#

코드 (python):

import sys
input = sys.stdin.readline

TC = int(input())

def unCrypt(sentence, s, m):
    """
    문제의 조건에 따라 생성된 암호문을 복호화하는 함수
    s: 암호의 시프트 값
    m: 블록 크기
    """

    # 시프트 복원
    shifted = ""
    for c in sentence:
        idx = ord(c) - ord('A')
        idx = (idx - s + 26) % 26 # 밀어서 암호화했으니 당겨서 복호화
        shifted += chr(idx + ord('A'))
    result = ""

    # 블록 단위 역순 복원
    start_idx = 0
    while start_idx < len(shifted):
        tmp = []
        for i in range(m):
            if start_idx + i < len(shifted): # 마지막 블록 조심
                tmp.append(shifted[start_idx + i])
        result += ''.join(tmp[::-1]) # 배열을 뒤집어서 join으로 합침
        start_idx += m
    return result

for _ in range(TC):
    N = int(input())
    sentence = ""
    for _ in range((N-1)//50 + 1): # 한줄에 최대 50글자
        line = input().rstrip()
        line = line.replace(" ", "")
        sentence += line
    crip = input().rstrip()
    flag = False
    for s in range(1, 26): # 1 <= s <= 25
        for m in range(5, 21):# 5 <= m <= 20
            if flag: # 이미 찾았으면 종료
                break
            if unCrypt(sentence, s, m).find(crip) != -1: # 복호화한 문장에 crib이 포함되어 있는지 확인
                print(s, m)
                flag = True
    if not flag:
        print("Crib is not encrypted.")
        

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

문제#

입력#

출력#

🧐 관찰 및 접근#

💻 풀이#