문제 설명
정수 n이 입력으로 주어졌을 때, 두 개의 n자리 수를 서로 곱하여 만들 수 있는 가장 큰 회문(팰린드롬)을 찾아야 합니다. 곱셈 결과가 지나치게 커질 수 있기 때문에, 최종 답은 1337로 나눈 나머지(mod 1337)를 반환합니다.
예를 들어 입력이 2라면 정답은 987입니다. 두 자리 수끼리의 곱 중 가장 큰 회문은 99 × 91 = 9009이며, 9009 mod 1337 = 987이기 때문입니다.
접근 방식
이 문제의 핵심 아이디어는 회문의 앞쪽 절반이 정해지면 뒤쪽 절반은 자동으로 결정된다는 점입니다. 따라서 만들 수 있는 회문을 큰 값부터 차례대로 생성하고, 각 회문이 두 n자리 수의 곱으로 표현되는지 검사하면 처음 조건을 만족하는 값이 곧 정답이 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- maxVal := 10n − 1 (n자리 수의 최댓값)
- minVal := maxVal / 10 (n자리 수의 최솟값)
- h를 maxVal부터 시작해 h > minVal을 유지하는 동안 1씩 감소시키며 반복합니다.
- left := h, right := 0으로 초기화합니다.
- i := h부터 i > 0까지, right = right × 10 + (i mod 10), left := left × 10, i := i ÷ 10 연산을 반복합니다. 이 과정을 통해 h의 자릿수를 뒤집아 회문을 조립할 준비를 합니다.
- x := left + right로 완전한 회문을 완성합니다. 예를 들어 h = 906이면 x = 906609가 됩니다.
- i를 다시 maxVal부터 i > minVal까지 감소시키며 다음을 검사합니다.
- i < x ÷ i이면 반복문을 빠져나옵니다. i가 √x보다 작아지면 더 이상 유효한 인수 조합이 존재하지 않기 때문입니다.
- x mod i == 0이면 x mod 1337을 즉시 반환합니다. 이는 해당 회문이 두 n자리 수의 곱으로 표현됨을 의미합니다.
- 조건을 만족하는 회문을 찾지 못한 경우를 대비해 9를 반환합니다.
회문을 내림차순으로 생성하므로 첫 번째로 성공하는 시점에 곧바로 종료할 수 있어, 모든 경우를 무작정 탐색하는 방식보다 훨씬 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int largestPalindrome(int n) {
int maxVal = pow(10, n) - 1;
int minVal = maxVal / 10;
for(int h = maxVal; h > minVal; h--){
lli left = h;
lli right = 0;
for(lli i = h; i > 0; right = right * 10 + i % 10, left*= 10, i/= 10);
lli x = left + right;
for(int i = maxVal; i > minVal; i--){
if(i < x / i) break;
if(x % i == 0) return x % 1337;
}
}
return 9;
}
};
main(){
Solution ob;
cout << (ob.largestPalindrome(3));
}
실행 결과
입력
3
출력
123
결과 해석
입력이 3일 때, 세 자리 수끼리의 곱으로 만들 수 있는 가장 큰 회문은 913 × 993 = 906609입니다. 프로그램은 이 값을 1337로 나눈 나머지인 123을 출력합니다.