백준 1341번: 사이좋은 형제

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

 

영식과 민식이가 케이크를 남아있는 양의 절반씩 먹을 때, 영식이가 먹게되는 케이크의 양이 분수로 주어진다. 분수에 해당하는 패턴을 구하는 문제이다. 분자는 a, 분모는 b 이다. 먹는 양의 총 합은 2^n -1 이므로 b의 배수 중에 2^n-1이 있는지 찾은 후 배수*a를 2진수로 변환하면 패턴이 된다.

 

우선, 예외 상황을 제거한다. a가 0이면 나머지를 민식이가 먹으므로 -을 출력하고 종료한다. b가 1이면 a도 1이므로 전부 영식이가 먹으므로 *을 출력한다.

if (a == 0) {
    System.out.print("-");
    return;
}
if (b == 1) {
    System.out.print("*");
    return;
}

 

 

이후, 배수를 구한다. 2^n -1을 b로 나누었을 때 나머지가 0이면 배수를 저장하고 멈춘다. 배수가 없으면 불가능한 경우이므로 -1을 출력하고 종료한다.

long m = -1;
int n = 0;
for (int i = 1; i <= 60; i++) {
    long pow = (1L << i) - 1;
    if (pow % b == 0) {
        m = pow / b;
        n = i;
        break;
    }
}

if (m == -1) {
    System.out.print(-1);
    return;
}

 

 

마지막으로, 배수*a 를 2진수로 표시 후 1은 *, 0은 -로 치환해주면 된다.

long t = m * a;
StringBuilder sb = new StringBuilder(Long.toBinaryString(t));
while (sb.length() < n) {
    sb.insert(0, '0');
}

for (int i = 0; i < sb.length(); i++) {
    sb.setCharAt(i, sb.charAt(i) == '1' ? '*' : '-');
}

System.out.print(sb);

 

 

결과 코드는 다음과 같다.

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

public class 사이좋은형제1341 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken()), b = Long.parseLong(st.nextToken());
        
        if (a == 0) {
            System.out.print("-");
            return;
        }
        if (b == 1) {
            System.out.print("*");
            return;
        }
        
        long m = -1;
        int n = 0;
        for (int i = 1; i <= 60; i++) {
            long pow = (1L << i) - 1;
            if (pow % b == 0) {
                m = pow / b;
                n = i;
                break;
            }
        }
        
        if (m == -1) {
            System.out.print(-1);
            return;
        }
        
        long t = m * a;
        StringBuilder sb = new StringBuilder(Long.toBinaryString(t));
        while (sb.length() < n) {
            sb.insert(0, '0');
        }
        
        for (int i = 0; i < sb.length(); i++) {
            sb.setCharAt(i, sb.charAt(i) == '1' ? '*' : '-');
        }
        
        System.out.print(sb);
    }
}