[BOJ 11068: 회문인 수] 수학 | C 언어

https://www.acmicpc.net/problem/11068

11068번: 회문인 수

회문

- 펠린드롬

- 거꾸로 읽어도 똑같은 것 

 

입력 받은 숫자를 2진법 ~ 64진법으로 표현했을 때 회문인 경우가 하나라도 있으면 1, 없으면 0을 출력하는 문제이다. 

 

진법

- 10진법 -> B진법으로 변환하기 : (숫자를 B로 나눈 나머지 값을 맨 뒤부터 놓고, 숫자를 B로 나눈다.) 반복

(개떡같은 설명 ...)

 

 

여기서 생각할 것은 숫자를 완전히 B진법으로 바꿀 필요가 없다는 것이다.

이 문제에서는 입력 값이 최대 1,000,000이긴 하지만 더 커질 경우 B진법 수를 다 계산하면 낭비낭비

 

회문 -> 가운데를 기준으로 똑같은 모양이다. 

그러니까 B진법으로 중간까지만 구하고, 그 다음부터는 나머지를 계산하고 바로바로 비교를 한다. 

중간에 하나라도 다르면 더이상 계산할 필요 없이 break 한다. 

 

 

중간까지만 구하기? 중간이 어디일까 

10진수를 B진법으로 변환했을 경우의 길이는 ceiling(log_B (10진수)) 

8을 2진수로 나타내면 1000 => 4자리 = log2 8 + 1

 

로그 계산

C언어의 <math.h> 에는 밑이 2인 로그를 계산해주는 함수가 있다. 

log2(num) -> double 형을 반환한다. 이 값을 int로 형변환을 해주면 알아서 뒤에는 버려지니까 + 1 해주면 된다. 

밑은 영원한 밑

공식 긴가민가해서 검색해봄..; 하튼 이렇게 변환해서 구하면 된다. 

 

 

 

코드

---

B진법으로 변환한 숫자를 저장할 배열 num_in_b는 [20]으로 선언했는데 문제에서 최댓값 1,000,000이고 2진수로 나타냈을 때 20자리 정도여러 이렇게 잡았다. 근데 어차피 반만 쓸거라서 [20]까지 필요 없다. 

int num;
scanf("%d", &num);

int num_in_b[20]; //B진법으로 나타낸 값을 저장할 배열
int rst;//회문이면 TRUE 

// B의 값의 범위 2 ~ 64
for(int b = 2; b <= 1<<6; b++) {
	rst = TRUE; 
    int temp = num;
    //B진법 자릿수 검사 
    int len = (int)(log2(temp)/log2(b)) + 1;

    for(int r = 0; r < len/2; r++) {
    	num_in_b[r] = temp % b;
        temp /= b; 
    }

    // 길이가 홀수인 경우 나눠주되, 기록은 하지 않음 
    if((len&1) != 0) temp /= b;

    // 채워진 배열의 뒷부분부터 같은지 검사한다.
    for(int s = len/2 -1; s >= 0; s--, temp /= b) {

	// 하나라도 다르면 현재 B는  FALSE
    	if(num_in_b[s] != temp % b){
            rst = FALSE;
	        break;
        } 
}

if(rst) {
    break;
  }     
}

printf("%d\n", (rst)? 1:0);