[BOJ #2231] 분해합

BOJ #2231, 분해합 문제입니다.

 

크게 어렵진 않은 문제이나, 새로운 접근 방법을 찾아내 공유할 겸 작성하게 되었습니다.

 

문제의 정의를 살펴 봅시다. a + a의 각 자릿수의 합 == b이면 a는 b의 생성자입니다. 처음에 이 관계가 잘 와닿지 않는데, a를 조작해서 b를 생성하므로 a가 b의 생성자라고 이해했습니다. 이런 사실들로부터 생각을 이끌어 보면, a에서 b를 구하는 것은 정말 쉽다는 것을 알 수 있습니다. 문제가 아무런 의미가 없게 되겠죠. 그렇지만 이 문제는 b에서 a를 구해야 하기 때문에 살짝 복잡해집니다. 왜냐하면 a == b이면서 동시에 a' == b일 수 있기 때문입니다.

 

이런 상황에서 가장 만만하게 써볼 수 있는 녀석이 완전탐색(Brute-Force)입니다. 멋있는 영어 이름도 있어서 대단해 보이지만 사실 가능한 모든 경우의 수를 다 해보는 것입니다. 그리고 실제로 이 문제는 완전탐색으로 풀립니다. 시간제한에 비해 입력 범위가 널널하기 때문입니다. (N <= 1,000,000) 그러나 만약 N의 범위가 더 커진다면 어떨까요? 예를 들면 N <= 1,000,000,000입니다. 이 경우엔 완전탐색을 하려면 최소 10억의 수 배, 혹은 수십 배의 연산이 필요할 것입니다. 시간이 절대적으로 부족해지겠죠.

 

완전탐색 이외의 해결책은 생각나지 않으므로, 완전탐색의 범위를 줄여 볼 생각을 해야겠죠. 저는 다음과 같은 사고과정을 거쳤습니다.

• b의 생성자가 a라고 하면, a + a의 각 자릿수의 합 == b
• 따라서 b는 무조건 a보다 작아야 함.
• a의 각 자릿수는 9를 넘을 수 없음.
• 따라서 b - b의 자릿수 * 9부터 b - 1까지만 완전탐색하면 됨.

특별할 것 없어 보이는 접근일 수 있으나, 이걸 캐치한 사람이 많지는 않은 것으로 보입니다. 저는 Python으로 풀었는데, Python으로 푼 거의 모든 사람들은 1000ms 이상 소요되었으나 제 코드는 60ms 소요되었습니다. 이 방식이면 N의 범위가 조 단위가 되어도(혹은 그 이상이어도...) 시간 내에 풀 수 있게 됩니다.