[백준/C++] 14561번 회문

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

14561번: 회문

문제 분석

n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. 예를 들면, 12468은 12468 = 1 × 104 + 2 × 103 + 4 × 102 + 6 × 101 + 8 × 100로 표현할 수 있다.

회문(Palindrome)이란 앞으로 읽으나 뒤로 읽으나 같은 글을 말한다. 예를 들면, madam, level, 12321은 회문이다.

어떤 십진수의 수 A가 주어졌을 때, 이를 n진수로 표현하면 회문인지 아닌지 판별하는 프로그램을 만드시오.

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1000)이 주어진다.

둘째 줄부터 T줄에 걸쳐 테스트 케이스별로 어떤 십진수의 수 A(1 ≤ A ≤ 100,000,000,000)와 n(2 ≤ n ≤ 16)이 공백을 두고 주어진다.

각 줄마다 테스트 케이스가 회문일 경우 1, 아닐 경우에는 0을 출력한다.

예제는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
long long int a,b;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> a >> b;

		vector<int> v;
		bool flag = false;

		while (true) {

			v.push_back(a % b);

			a /= b;
			if (a == 0) break;
		}
		vector<int>::iterator left;
		vector<int>::iterator right;

		left = v.begin(); right = v.end()-1;

		while (left <= right) {
			if (*left == *right) {
				left++;
				right--;
				continue;
			}
			else {
				flag = true;
				break;
			}
		}
		if (flag) {
			cout << "0\n";
		}
		else {
			cout << "1\n";
		}
	}
}

문제 풀이

1. 우선 십진수와 문제에서 요구하는 진법을 하나식 읽어들인다.

2. 예전 수학시간에 2진수 직접 구하기 할 때 처럼, a 나누기 b한 나머지를 벡터 v에 하나씩 넣는다.

3. 그리고 a 나누기 b를 진행하며 a가 0, 즉 더 이상 나눌 수 없을 때 까지 진행한다.

4. 2~3번의 과정을 계속 진행하다보면 각 십진수를 문제에 주어진 진법의 수로 변환할 수 있다.

5. 벡터를 탐색할 반복자(iterator)를 두개 선언 해준 뒤, 각각을 벡터의 처음(0)과 끝(v.size()-1) 인덱스 값으로 할당해준다.

6. left가 right보다 작거나 같을 때 까지 반복하며(=벡터의 왼쪽과 오른쪽부분이 동일한지 비교하기 위해)

두개의 반복자가 가리키는 값이 같으면(=회문이면) 값을 증가,감소시키며 계속 검사하고, 만약 하나라도 다르다면 바로 break하고 flag를 세워준다.

7. flag값에 따라 정답을 출력한다.

​

※양수의 최대값은 2,147,483,647 으로 10자리를 넘는 값을 표현 할 수 없다.

문제에서 가능한 수의 범위는 100,000,000,000이므로 그냥 INT형으로 선언하게 될 경우,

런타임에러(DivideByZero)에 걸릴 수도 있다는 사실에 유의하자!!