숫자 n이 주어졌을 때, n개의 행으로 구성된 삼각형을 만들어야 합니다. 각 행에는 회문(팰린드롬) 형태의 수가 포함됩니다.
예를 들어 입력값이 n = 5라면, 출력 결과는 다음과 같습니다.
1 121 12321 1234321 123454321
해결 방법
이 문제는 의외로 간단한 수학적 원리로 해결할 수 있습니다. 다음 단계를 따릅니다.
- 1부터 n까지 반복합니다.
- ((10^i) − 1)의 정수 부분을 9로 나눈 값의 제곱을 출력합니다.
- 다음 줄로 넘어갑니다.
여기서 핵심 아이디어는 레푸닛(repunit) 수입니다. 10의 거듭제곱에서 1을 뺀 값을 9로 나누면 1, 11, 111, 1111처럼 모든 자릿수가 1인 수가 됩니다. 이러한 수를 제곱하면 1×1=1, 11×11=121, 111×111=12321처럼 자연스럽게 좌우 대칭인 회문 수가 완성됩니다.
예제 코드
다음 구현 예시를 통해 더 쉽게 이해할 수 있습니다.
def solve(n):
for i in range(1,n+1):
print((((10**i) - 1)//9)**2)
n = 8
solve(n)입력
8
출력
1 121 12321 1234321 123454321 12345654321 1234567654321 123456787654321
위 코드는 n이 9 이하일 때 올바른 회문 삼각형을 출력합니다. 참고로 n이 10 이상이 되면 자릿수 올림(carry) 때문에 대칭 구조가 깨지므로, 문자열 연결 방식을 사용하는 것이 더 안전합니다.