백준 33887 (C++) Was It a Cat I Saw

최초 업로드: 2025-11-24 14:24:57

최근 수정 시간: 2025-11-24 14:24:57

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] Was It a Cat I Saw

[문제 링크](https://www.acmicpc.net/problem/33887)

## 문제 설명

문제 제목의 문장을 거꾸로 읽어보자. 그렇다. 당신은 팰린드롬을 좋아한다.

팰린드롬(Palindrome)이란 앞으로 읽어도, 뒤로 읽어도 같은 문자열을 의미한다. 양의 정수 $X$가 주어질 때, 당신은 연산마다 아래의 연산 중 하나를 골라 시행할 수 있다.

$X$를 이진수로 표현한 문자열이 팰린드롬이 되도록 원하는 만큼 연산을 적용할 때, 필요한 연산의 최소 횟수를 구해보자. 이때 $X$를 이진수로 표현했을 때 앞쪽의 불필요한 $0$들(leading zero)은 무시한다. 예를 들어, $X=9=1001_{(2)}$는 이진수로 표현했을 때 팰린드롬이지만, $X=8=1000_{(2)}$는 이진수로 표현했을 때 팰린드롬이 아니다.

## 입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T \leq 30)$

두 번째 줄부터 $T$줄에 걸쳐 양의 정수 $X$가 주어진다. $(1\leq X \leq 10^9)$

## 출력

각 테스트 케이스마다 $X$를 이진수로 표현한 문자열이 팰린드롬이 되도록 문제의 연산을 적용할 때, 필요한 연산의 최소 횟수를 출력한다.

## 풀이

``` c++
#include<bits/stdc++.h>
using namespace std;

bool isPalindrome(string s) {
    if(s.find('1')==s.npos) return true;
    s = s.substr(s.find('1'));

for(int i=0;i<s.length()/2;i++) {
 if(s[i]!=s[s.length()-1-i]) return false;
 }
 return true;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int x; cin >> x;
 for(int i=0;;i++) {
 if(isPalindrome(bitset<32>(x+i).to_string()) || isPalindrome(bitset<32>(x-i).to_string())) {
 cout << i << '\n';
 break;
 }
 }
 }
}
```