글 읽기 - [힌트] 문제 접근 방법과 아이디어, 소스코드 입니다,

helios789789 3년 전 3

이문제는 소수의 이진수 표현 방법과 밀접한 관련이 있습니다.

소수의 이진수 표현 방법을 모르신다면 검색해보시길 추천드립니다.

60자리 이하의 패턴으로 매칭하지 못하는 경우는 주어진 분수를 이진수로 변환했을때

소숫점 120자리 이하의 소수로 딱 맞아 떨어지거나, 소수점 120자리 이상이지만 유한소수인 경우 입니다.

밑의 코드에서 주어진 분수가 유한소수인지, 120자리 이하에서 딱 맞아 떨어지는지를 확인하는것을 볼 수 있습니다.

120자리 이상의 무한 소수라면, 이제 패턴매칭을 해주면 됩니다.

맨 처음에는 등비수열의 합 으로 접근하였는데, b 의 범위가 long long 의 max 값인 2^63 - 1 까지 이므로 소숫점 아래 60자리의 소수인 경우 등비수열의 합을 계산하는데 오버플로우가 나서 다른 방법으로 접근하였습니다.

a / b 꼴 을 소수로 바로 변경하면 부동소숫점 오차가 발생할 수 있어, 계속 분수의 형태를 유지하면서 계산하는 방법에 유의하시길 바랍니다.

1 / 2 와 컴퓨터가 표현하는 0.5 는 오차가 발생할 수 있습니다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <string.h>
#include <math.h>
#include <cassert>
#pragma warning(disable:4996)
using namespace std;


const int INF = 987654321;
unsigned long long origin_a, a, b;
bool isInfinite = false;

string ret;
void solve() {
	// a/b 가 0 이거나 1 일때의 예외 처리
	if (a == 0) {
		cout << "-" << endl;
		return;
	}
	if (a == b) {
		cout << "*" << endl;
		return;
	}

	// 순환소수 인지 판명을 위한 변수
	origin_a = a;

	// 패턴의 최장 길이가 60 이니, 소숫점 120 자리 까지는 알아야 함
	while (a != 0 && ret.length() < 120) {

		// 순환소수 인 경우 표시
		if (origin_a == a)
			isInfinite = true;

		// 소수의 이진수 표현
		a += a;

		if (a >= b) {
			ret += "1";
			a -= b;
		}
		else
			ret += "0";

	}

	// 소숫점 아래 120자리 이하의 유한소수 이거나,
	// 소숫점 아래 120자리 이상이지만 순환소수가 아닌 경우
	// 60자리 이하로 패턴 매칭을 할 수 없다
	if (ret.length() < 120 || isInfinite == false) {
		cout << "-1" << endl;
		return;
	}

	// 60자리 까지 패턴을 매칭시켜 봄
	for (int i = 1; i <= 60; i++) {

		string s = ret.substr(0, i);

		for (int j = i; j + i <= 120; j += i)
			// 패턴 불일치
			if (ret.substr(j, i) != s) {
				s = "#";
				break;
			}

		// 패턴 일치
		if (s != "#") {
			for (int j = 0; j < s.length(); j++)
				s[j] = (s[j] == '1') ? '*' : '-';

			cout << s << endl;

			return;
		}
	}


	cout << "-1" << endl;
}

int main() {
	cin >> a >> b;


	solve();

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.