[Jungol] 정올 1097 앞뒤 같은 제곱

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=377&sca=2020

Approach

앞뒤 같은 수를 회문(Palindrome)이라고 합니다.

회문 여부를 확인할 때는 양끝에서 진행하여 범위를 좁혀오며 확인할 수 있습니다.

ex) 1 2 3 2 1

(즉, 양끝(i, j)에서 i++ j-- 처리하여 각각 →, ← 방향으로 이동.)

 

1 ≤ N ≤ 300 범위 수를 제곱한 수를 P (= N2 )라고 했을 때,

P를 B진법 수로 만들기 위해 Horner's method를 역으로 적용

(P를 B진법 수로 만든 결과는 문자를 포함할 수 있다.)

- 각 Test Case마다 초기화 유의

- N은 회문이 아니어도 P는 회문이어야 합니다.

---

#include <stdio.h>

int B;
char strA[99], strB[99];

int isPalindrome(char *str, int i, int j) {
    while (i < j && str[i] == str[j]) ++i, --j;
    return i >= j;
}

void reverse(char *s, char *t) {
    for (; s < t; ++s, --t) {
        char ch = *s;
        *s = *t;
        *t = ch;
    }
}

int convert(char *str, int n, int k) {
    if (n < B) {
        str[k] = (char)((n > 9) * 7 + 48 + n);
        str[k + 1] = 0;
        reverse(str, str + k);
        return isPalindrome(str, 0, k);
    }

    int r = n % B;
    str[k] = (char)((r > 9) * 7 + 48 + r);
    return convert(str, n / B, k + 1);
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &B);
    for (int i = 1; i < 301; ++i) {
        if (convert(strB, i *i , 0)) {
            convert(strA, i, 0);
            printf("%s %s \n", strA, strB);
        }
    }
}