[BOJ/백준] 11288번 : Ethel’s Encryption (Java)

📘 백준 11288번 : Ethel’s Encryption

---

문제 바로가기

🔤 문제 번역

문제

에텔은 북부 동맹(NSA)이 자신과 언니 루시(Lucy)의 통신을 감청하고 있다고 의심했다. 이를 막기 위해 에텔은 모든 통신 내용을 카이사르 암호(Caesar cipher)를 사용해 암호화했다.

카이사르 암호란, 평문의 각 알파벳 문자를 일정한 오프셋만큼 이동시켜 암호문을 만드는 방식이다.
예를 들어 오프셋 값이 2라면, A는 C가 되고, B는 D가 되며, Y는 A가 된다.

당신의 임무는 오프셋 값이 a^b로 계산된다는 사실이 주어졌을 때, 에텔의 암호화된 메시지를 복호화하는 것이다.

입력

첫 번째 줄에는 세 개의 정수 n, a, b가 주어진다.

• n은 암호화된 메시지의 문자 개수이며, 공백을 포함한다.
• a와 b는 오프셋 a^b를 계산하는 데 사용된다.
  • 0 ≤ a ≤ 2^31
  • 0 ≤ b ≤ 2^16
  • 단, 각 입력마다 a 또는 b 중 적어도 하나는 0보다 크다.

두 번째 줄에는 n개의 문자로 이루어진 암호화된 메시지가 주어진다.
이 문자열은 대문자 알파벳(A–Z) 또는 공백만 포함하며, 입력 줄 끝에는 개행 문자가 포함된다.

출력

복호화된 메시지를 대문자 알파벳으로 한 줄에 출력한다.
공백은 암호문과 동일한 위치에 그대로 유지해야 한다.
출력 마지막에는 개행 문자가 포함되어야 한다.

💡 문제 풀이

---

암호화는 각 알파벳을 오프셋만큼 앞으로 이동시키는 방식이며, 복호화는 그 반대로 오프셋만큼 뒤로 이동.

오프셋은 a^b로 주어진다. 하지만 a^b는 매우 커질 수 있으므로 그대로 계산하면 오버플로우가 발생한다.
카이사르 암호는 알파벳 26자를 순환하므로 실제로 필요한 값은 다음과 같다.

• offset = (a^b) mod 26

a와 b의 범위가 크기 때문에 거듭제곱을 진행하는 동안 매번 mod 26을 적용해서 오프셋을 계산. 입력으로 받은 a는 먼저 a % 26으로 줄인 후 a를 b번 곱하는 걸 반복하면서 mod 26도 곱할 때마다 반복.

offset = (offset * a) % 26

복호화는 문자를 0~25로 매핑: x = c - 'A'한 후, 뒤로 offset만큼 이동: x - offset 음수 방지를 위해 +26을 더해준 뒤 mod 26 수행 다시 문자로 복원: + 'A'

즉, (c - 'A' + 26 - offset) % 26 + 'A'

✅ 코드 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/11288
// a^b mod 26 = (a mod 26) ^ b (곱할 때 마다 mod 반복)
// 복호: 'A'를 0으로 만들고 offset 만큼 뒤로 민 후 0 ~ 26 사이로 만든 후, 다시 'A'를 65(아스키)로 만든 후 출력 저장
public class B11288_Ethel_s_Encryption {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken()); // 암호화된 메시지의 문자 개수 (공백 포함)
		long a = Long.parseLong(st.nextToken()) % 26; // 오프셋을 계산하는 데 사용되는 값
		long b = Long.parseLong(st.nextToken());
		long offset = 1; // 오프셋
		for (int i = 0; i < b; i++) {
			offset *= a;
			offset %= 26;
		}
		String s = br.readLine();
		for (int i = 0; i < n; i++) {
			char c = s.charAt(i);
			if (c == ' ') { // 공백 스킵
				sb.append(c);
			} else { // 복호
				sb.append((char) ((c - 'A' + 26 - offset) % 26 + 'A'));
			}
		}
		System.out.println(sb);
		br.close();
	}
}

💾 제출 결과

---

보러 가기