BOJ 1341 사이좋은 형제

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

1341번: 사이좋은 형제

 

처음 생각한 방법은 주어진 분수를 무한 등비급수로 표현할 수 있는 방법이 있는지 생각해봤다.
아무리 생각해도 그런 방법은 떠오르지 않아서 다른 방법으로 접근해봤다.

새로 접근한 방법은 소수의 2진수 표현이다. 1/2, 1/4, 1/8, 1/16 ... 으로 나가는 것이 소수를 2진수로 표현하는 방법에서 봤던 것 같아 해당 방법으로 계획을 세웠다.

a/b (a,b는 10진수) 를 2진수 소수로 바꾸는 방법은 다음과 같다.

0. 0. 에서 시작한다.
1. 분자에 2를 곱한다.
2. 해당 분수가 1이 넘는지 아닌지 확인한다. 1을 넘기면 1, 넘기지 않으면 0을 붙인다.
3. 1을 넘기면 분자에 분모를 빼준다.
4. 1을 반복한다.

2/3 을 예로 들어보자.

0. 0.에서 시작한다.
1. 분자에 2를 곱한다.(4/3)
2. 1이 넘으므로 1을 붙인다 (0.1)
3. 분자에 분모를 빼준다(1/3)
1. 분자에 2를 곱한다.(2/3)
2. 1을 넘지 않으므로 0을 붙인다. (0.10)
1. 분자에 2를 곱한다(4/3) <- 반복됨

이런 식으로 반복되는 구간을 찾으면 해당 문제를 풀 수 있다.

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

typedef unsigned long long ull;
using namespace std;

int main(){
    ull a, b, c; scanf("%llu%llu",&a, &b);
    if(b%2) c = b/2 + 1;
    else c = b/2;
    vector<ull> v;
    string s = "";
    vector<ull>::iterator iter = v.end();
    while(v.size() <= 60){
    	
        vector<ull>::iterator t = find(v.begin(), v.end(), a);
    	if(t != v.end()){
            iter = t;
            break;
        }
        else v.push_back(a);
        
        if(a >= c) s += "*";
        else s += "-";
        if(a > b){
        	a -= b;
        	a *= 2;
        }
        else{
        	a = b-a;
        	if(b >= 2*a) a = b-2*a;
        	else a = b - 2*a + b;
        }
    }
    if(iter == v.begin()) printf("%s\n",s.c_str());
    else printf("-1\n");
    
    return 0;
}

 

여기서 주의해야할 점은 분자에 2를 곱할 때 unsigned long long 범위를 넘어가는 것이다.
나는 a = a-b (mod b) 를 이용하여 문제를 풀었다.
근데, 내 코드에서도 문제가 될 만한 부분이 있는데, 통과를 한 것이 좀 신기하다.

다른 분들은 이런 처리를 하지 않고 깔끔하게 풀었다.
문제를 풀어서 직접 참고해보자.