[Project Euler #4][C++] 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

문제4 : 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

문제

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

문제 해결 방법

팰린드롬 찾기 알고리즘 을 이용하여 문제를 해결하였다.

• 우선, 팰린드롬 검사 함수(bool findPalindrome(string ary))를 만들었다.
• 2중 for 문을 사용하여 100부터 999까지 순회를 하면서 곱한 수를 string형으로 바꾼 후(to_string(i * j)), 하나하나씩 팰린드롬 검사를 수행하였다. (findPalindrome(to_string(i * j))
  • 곱한 수가 팰린드롬일 경우, 그 때의 숫자들(i와 j)을 각각 firstNum, secondNum 변수에 대입하였다.
    • sum 변수를 사용하여 최댓값이었을 때의 숫자가 대입되도록 하였다.
• 최종적으로 firstNum, secondNum, sum이 출력되도록 하였다.

소스 코드

#include <iostream>
#include <string> // to_string()
#include <cmath>  // pow()
using namespace std;
 
#define DIGITS 3   // DIGITS 자리 수를 곱해 만들 수 있는 가장 큰 대칭수                                                                  
 
bool findPalindrome(string ary);
 
int main() {
    int firstNum, secondNum, sum = 0;
    bool palindrome = true;
 
    for (int i = pow(10, DIGITS - 1); i < pow(10, DIGITS); i++) {
        for (int j = pow(10, DIGITS - 1); j < pow(10, DIGITS); j++) {
            if (findPalindrome(to_string(i * j))) {
                if (sum < i * j) {  // 최댓값 찾기
                    sum = i * j;
                    firstNum = i;
                    secondNum = j;
                }
            }
        }
    }
    cout << firstNum << " * " << secondNum << " = " << sum;
 
    return 0;
}
 
bool findPalindrome(string ary) {
    bool isSame = true;
    for (int i = 0; i < ary.length(); i++) {
        if (ary[i] == ary[ary.length() - 1 - i]) {
            continue;
        }
        else {
            isSame = false;
        }
    }
    return isSame;
}

정답

906609

심화 공부

대칭수(Palindrome)

순서대로 읽은 수와 거꾸로 읽은 수가 같은 수를 말한다. 예를 들어 34543은 대칭수이고, 34567은 대칭수가 아니다. 대칭수는 유희 수학에서 주목받는 수이며, 일반적으로 어떤 성질을 가지는 동시에 대칭인 수를 다룬다. 예로 0, 1, 14641, 104060401, 1004006004001, ...은 네 제곱인 대칭수이다. 회문수(回文數) 라고도 한다.

---

문제 출처 : https://euler.synap.co.kr/problem=4