멤고리즘 2회 2번. 이진회귀수

두현이의 음모

문제

단기회식 때 술게임으로 만취가 되어버린 두현이가 자신에게 술을 먹인 회원들에게 새로운 술게임을 통해

복수하려 한다. 게임의 룰은 이렇다.

10진수를 상대방에게 말하면 2진수로 좌우 대칭(이진 회귀수)이 맞는지 1초 안에 대답하는 게임이다.

예를들어 10진수 21은 2진수로 10101 이므로 이진회귀수이다.

두현이는 알딸딸한 상태에서도 게임의 승률을 높이기 위해 A와 B 사이에 해당하는 이진회귀수를 출력해 외우려 한다.

 

입력

A B  (2 <= A, B <= 100000) 

출력

A와 B 사이에 존재하는 2진 회귀수

예제 입력1

1 10

예제 출력1

1
3
5
7
9

---

[문제 설명]

2진수의 중간을 기점으로 양쪽을 비교하여 좌우 대칭을 이루는 수를 이진회귀수라고 부릅니다.

예를들어 11011, 101010101도 이진회귀수겠죠?

이번 문제에서는 입력으로 두 개의 숫자가 들어오게 되고, 그 숫자사이의 이진회귀수를 찾는 문제입니다.

입출력으로는 2진수가 아닌 10진수로 나타내야하는 것을 알아두셔야 합니다.

[소스코드 설명]

저같은 경우, 일단 while문을 돌면서 각 숫자를 2진수로 바꿔주었습니다.

그 후 2진수 문자의 길이의 절반만큼 for문을 돌면서 앞과 뒤를 비교하였습니다.

이 때 check라는 flag를 두어서 앞과 뒤가 같지 않을경우  check=0을 줘서 이진회귀수가 아님을 체크하였습니다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <stdio.h> #define MAX 1000   int first = 1;   void find(int n) {     int num[MAX];     int tmp = n;     int count=0;     int check = 1;          while(n>=1) {         num[count++] = n % 2;         n = n/2;     }       for(int i=0; i<count/2; i++)         if(num[i] != num[count - 1 -i])         {             check = 0;             break;         }       if(check){         if(first){             printf("%d", tmp);             first = 0;         } else             printf("\n%d", tmp);     } }   int main() {     int A, B;       scanf("%d%d", &A, &B);       for(int i=A; i<=B; i++)         find(i);       return 0; }