백준 1341: 사이좋은 형제

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

 

등비수열의 합?

지금까지 알고리즘 문제를 풀면서 무한이란 개념을 접할 기회가 적었다. 그렇기에 처음 보았을 떄엔 많이 당황하였다.

대학 1학년 시절 이후에 미분 / 적분, lim은 오랜만에 보았으니..

 

그럼에도 문제의 표를 천천히 관찰한 결과, 등비수열의 합으로 문제를 해결할 수 있지 않을까? 란 가정을 하였다.

아이디어는 다음과 같다.

 

처음의 영식이가 먹을 턴이 돌아올 때, 이전에 먹은 케이크의 양은 한 번 돌아올때까지의 길이의 반비례한다.

즉, 양비수열이다. 그렇다면, 첫 턴에 먹은 케이크 양을 a, 패턴 반복 까지의 길이를 r이라 칭할 때,

lim의 양비수열은 a / (1 - (1 / pow(2, r))) 이렇게 계산할 수 있다. 그렇다면 이렇게 구현을 할 수 있다.

 

1 ~ 60까지의 패턴 반복을 시험한다.

각각의 초기값은 (1 / pow(2, i))로 구할 수 있고, 다음 자신이 먹을 케이크의 양은 이전의 (1 / pow(2, 문자열 길이)) 이렇게 된다.

 

만약 구한 값이 현재 값보다 크면 0이고, 작거나 같으면 1이고 현재 값에서 뺀다.

이런식으로 구할 수 있지 않을까? 생각했었다.

 

#include <iostream>
#include <cmath>

using ll = long long;
ll a, b;
using namespace std;
string ans = "";

int main()
{
	cin >> a >> b;
	for (int i = 1; i <= 60; i++)
	{
		double a = 1, r = 1 / pow(2l, i), s = (double) a / b;
		string tmp = "";
		for (int j = 0; j < i; j++)
		{
			a /= 2;
			double exp = a / (1 - r);
			if (exp > s)
			{
				tmp.push_back('-');
			}
			else
			{
				tmp.push_back('*');
				s -= exp;
			}
		}
		if (s == 0.)
		{
			ans = tmp;
			break;
		}
	}
	if (ans.empty()) cout << -1 << '\n';
	else cout << ans << '\n';
	
}

결과는 보기 좋게 틀렸다.  이것으론 예제 입력 2를 통과하지 못한다.

이유는 기본 자료형인 double이 생각 이상으로 소수를 부정확하게 계산해서, 오차가 생겼기 때문이다.

그렇다면 오차를 어느정도 허용할 것인가를 생각해야하는데, 이것을 정하는 것은 힘들다.

 

그렇다면 분수의 형태를 유지해서 계산하면 어떨까?

그것도 안 된다. 가장 큰 이유는 A, B가 C++에서 제공하는 최고 값을 저장할 수 있는, long long 타입의 max 값에 근접하기 때문이다.

분수의 형태를 유지하려면

 

1. 분수 간의 뺄셈을 해야한다.

2. 분수 간의 대소관계를 명확히 해야한다.

 

이 두가지가 필요한데, 적어도 내가 아는 내에선 1, 2 둘다 곱셈이 사용되기에 가볍게 long long 타입을 넘는다.

그렇다면 다른 방법이 필요하다.

 

해결법

이 문제의 정의를 다시해보자. 이 문제를 식으로 하면 다음과 같이 쓸수 있다.

 

A / B = (1 / 2) * a ₀ + (1 / 4) * a ₁ + (1 / 8) * a ₃ + (1 / 16) * a ₄ ....

 

여기서 a의 원소는 1 혹은 0이다.

수열 a가 반복되는 것을 찾아야한다.

 

만약 여기서 2를 곱하면 어떻게 될까?

 

(2 * A) / B = a ₀ + (1 / 2) * a ₁ + (1 / 4) * a ₃ + (1 / 8) * a ₄ ....

만약 a ₀가 1이면, (2 * A) / B 를 가볍게 넘긴다. 아니라면 a ₀는 0이다.

그렇다면 매법 (A / B)에 2를 곱하면서 해당 원소가 1을 넘기는 확인하고, 아니면 0, 그렇다면 1이로 정한 뒤, a _i 즉, 1을 빼며 다음 원소를 구하면 된다!

그 뒤에 반복되는 패턴이 있는지 확인한다.

처음에는 아무 생각없이 set을 사용했었는데

#include <iostream>
#include <set>

using ll = unsigned long long;
using namespace std;
set<ll> S;
ll A, B;
string ans = "";
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> A >> B;
	S.insert(A);
	if (A == B) ans = "*";
	else
	{
		while (ans.size() <= 60)
		{
			if (A == 0)
			{
				ans = "-1";
				break;
			}
			A += A;
			if (A >= B)
			{
				ans.push_back('*');
				A %= B;
				if (S.find(A) != S.end()) break;
				S.insert(A);
			}
			else
			{
				ans.push_back('-');
				if (S.find(A) != S.end()) break;
				S.insert(A);
			}
		}
	}
	if (ans.empty()) ans = "-";
	if (ans.size() > 60) ans = "-1";
	cout << ans << '\n';
}

제출한 뒤에, 틀렸다는 것을 알고 다시 생각을 한 결과, 문자열을 120까지 늘여놓은 뒤에 1 ~ 60까지 처음부터 문자열을 확인해서, 패턴이 반복되는지 확인하는 작업을 추가하였다.

 

필자의 경우엔 1~60 길이의 문자열을 자른 뒤에, 길이가 120을 넘을 때까지 문자열을 반복한 뒤에, 길이를 딱 120으로 잘라서, 원래의 문자열과 비교했다. 

 

A와 B가 같은 경우, A가 0인 경우 등의 예외를 처리하는 것도 잊지말자.

#include <iostream>
#include <set>

using ll = long long;
using namespace std;
set<ll> S;
ll A, B;
string ans = "";
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> A >> B;
	S.insert(A);
	if (A == B) ans = "*";
	else if (A == 0) ans = "-";
	else
	{
		while (ans.size() < 120)
		{
			if (A == 0)
			{
				ans = "-1";
				break;
			}
			if (B / 2 < A)
			{
				ans.push_back('*');
				A = A + (A - B);
			}
			else
			{
				ans.push_back('-');
				A = (A + A) % B;
			}
		}
		for (int i = 1; i <= 60; i++)
		{
			string pattern(ans.begin(), ans.begin() + i);
			string str = "";
			while (str.size() < ans.size()) str += pattern;
			if (string(str.begin(), str.begin() + ans.size()) == ans)
			{
				ans = pattern;
				break;
			}
		}
		if (ans.size() > 60) ans = "-1";
	}
	cout << ans << '\n';
}

골드 3이지만, 동 난이도 다른 문제들보다 많이 헤맨 문제였다.

그럼에도 재미있었던 문제였다.