Project Euler #4

Project Euler #4

---

• 문제
  
  • 풀이 1
  • 풀이 2
• 후기

문제

---

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

대칭수(회문수)는 어느쪽으로 읽어도 동일한 수를 말한다.

두 2자리 수의 곱으로 만들수 있는 가장 큰 대칭수는 9009 = 91 × 99 이다.
두 3자리 수의 곱으로 만들수 있는 가장 큰 대칭수를 찾아라.

풀이 1

---

• for로는 루핑시켜서 값을 구했다.(노가다)
• 두 3자리 수의 곱 중 대칭수가 되는 가장 큰 수를 출력하는 형태로 진행된다.
• 약 0.8초대의 수행시간이 나온다.

import time
nl = list(range(999, 99,-1))                #3자리 수로 이루어진 리스트 생성
rs1 = 0
rs2 = 0
sol = [0, 0]
stime = time.time()                         #시작 시간

for i in nl:
    for j in nl:
        rs1 = i * j
        ck = str(rs1)
        if ck == ck[::-1] and rs1 > rs2:    #두 수의 곱의 정순, 역순 비교 및 대소 비교
            sol[0] = i
            sol[1] = j
            rs2 = rs1
            break

print (rs2, sol)                            #결과 출력
print(time.time() - stime)                  #소요 시간

풀이 2

---

• 두 3자리 수 곱의 최대값(998001) 이하의 대칭수 중 3자리 수 곱으로 이루어진 수를 출력한다.
• 최대값에서 역순으로 대칭수를 구해 이 중 3자리 수 곱으로 이루어지면 빠져나온다.
  때문에 가장 큰 대칭수를 따로 구할 필요가 없으며 수행 횟수도 줄어든다.
• 약 0.2초 대의 수행시간이 나온다.

import time
num = 999 * 999                                     #두 3자리 수의 곱의 최대값
sol = [0, 0]
stime = time.time()                                 #시작 시간

while True:
    if str(num) == str(num)[::-1]:                  #대칭여부 확인
        for i in range(999, 99, -1):                #range 함수를 사용한 3자리 수 입력
            if num % i == 0 and num // i < 1000:    #3자리 수로 나누어 떨어지면서 그 몫이 3자리인 수
                sol[0] = i
                sol[1] = num // i
                break
    if sol != [0, 0]:
        break
    num -= 1

print(num, sol)                                     #결과 출력
print(time.time() - stime)                          #소요 시간

후기

특별히 수학적인 설명이 필요한 부분은 없어 보인다.