BOJ 1341 - 사이좋은 형제

문제

\(0\le{a}\le{b}\le{2^{63}-1}\), \(\text{gcd}(a, b)=1\)인 정수 a, b가 주어진다.
점화식이 \(a_n=\frac{1}{2}\cdot{(\frac{1}{2})}^{n-1}\) 인 무한 등비 수열에 대해 특정한 패턴에 따라서 A, B가 번갈아가며 항을 차지할 때, A가 가지는 모든 항의 합이 a/b가 되도록 하는 패턴을 구해야 한다.
패턴의 길이가 60보다 크거나 아예 존재하지 않으면 -1을 출력하고, 가능한 패턴이 여러 가지면 가장 짧은 것을 출력해야 한다.

풀이

이진수로 표현했을 때 나누어 떨어지면 유한 소수가 되어 패턴을 정의할 수 없기 때문에 예외 처리를 해줘야 한다.

주어진 정수 \(b\)에 대해 \(mb=2^n-1, n\in\Bbb{N}\)을 만족하는 정수 \(m\)이 존재한다.
이러한 \(m\)은 여러 개가 있을 수 있는데, 각각 길이가 \(n\)인 패턴을 의미한다.

패턴이 계속 반복되기 때문에, 하나의 구간에서의 A의 비율은 전체 구간에서의 A의 비율과 같다.
따라서 \(\frac{a}{b}=\frac{ma}{mb}\)이고, \(ma\)을 이진수로 변환한 값이 패턴이 된다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        long a = Long.parseLong(input[0]), b = Long.parseLong(input[1]), t = 0, m = -1;
        int n = 0, f=0;
        if (a == 0) {
            System.out.println('-');
            return;
        }
        if (b == 1) {
            System.out.println('*');
            return;
        }
        if (a<b-a) {
            a = b - a;
            f = 1;
        }
        while(n<=60){
            t = (long) Math.pow((double) 2, (double) n);
            n++;
            if(b>t) continue;
            else if(b==t) break;
            else if ((t - 1) % b == 0) {
                m = (t-1) / b;
                break;
            }
        }
        if(m==-1){
            System.out.println(-1);
            return;
        }
        t = m * a;
        StringBuilder st = new StringBuilder(Long.toBinaryString(t));
        if (f==1) {
            for (int i = 0; i < st.length(); i++) {
                st.replace(i, i + 1, Integer.toString('1' - st.charAt(i)).substring(0, 1));
            }
        }
        for (int i = 0; i < st.length(); i++) {
            if (st.charAt(i) == '1') st.replace(i, i + 1, "*");
            else st.replace(i, i + 1, "-");
        }
        System.out.println(st);
    }
}

• a가 0일 경우, b가 1일 경우를 순서대로 확인하면서 0, b, 0, 1, 1, 1을 예외 처리했다.
• \(a\le{b-a}\)일 경우 패턴의 앞의 몇 자리가 0이기 때문에 계산하는 과정에서 없어진다.
  • 앞의 조건을 만족할 경우 a를 b-a로 바꾸고, 이후에 다시 0과 1을 스왑해서 해결했다.
  • 어차피 n이 자리수이기 때문에 n과 st.length()가 다르면 앞의 자리를 '-'로 채우는 방법으로 해결할 수도 있다.

풀고나서

• 프로그래머스에서도 계속 자바로 풀고 있지만, 형 변환이랑 변수 reassign을 잡는건 적응이 되지 않는다.
• 이제 계속 자바로 풀 예정이라 VSCode 익스텐션을 깔았는데, Main 중복 에러 때문에 파일이 빨갛게 변하길래 그냥 익스텐션을 껐다. 실행은 Intellij로 해야겠다.
• 기본 언어가 C++ 11로 설정되어 컴파일 에러를 몇 번 받았다.