[BOJ_1188] 음식 평론가

설명

---

아래 그림처럼 접근했다. 16 6 들어오면 8 / 3 까지 기약 분수 형태로 GCD로 나눌 수 있고 이때 6개들은 그냥 배포하고 나머지 2/3에 대해서 정리하는 형태로 접근했다.

아래 그림을 보면 밑의 코드가 이해가 될 것이다.

 

N = 2 , M = 5 2/5씩 하는데 이를 빼서 보면 4등분으로 나온다. 2/5 2/5 1/5 1/5 2/5 2/5

 

그러고 보니, 분자 만큼 나누어야 (2개의 빵을 5등분을 하려면 -> 4번 짜른다. 이렇게 생각하면된다.) 하는데 칼질의 갯수니 -1을 하면된다.

 

추가로, 마지막에 GCD로 나눈 기약분수 형태로 풀었으니 다시 복구 시켜야한다.

 

코드

---

package Math;

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

public class BOJ_1188 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        while(M <= N){
            N -= M;
        }
        if(M == 0){
            System.out.println(0);
        }else {
            int down = (M / GCD(M,N) - 1);

            System.out.println(down * GCD(M,N));
        }
    }
    private static int GCD (int a, int b){
        if (b == 0){
            return a;
        }
        return GCD(b,a%b);
    }
}

 

1188번: 음식 평론가