백준 1188번. 음식 평론가

서론

오늘의 썸네일

열공하자! (출처: 최고심)

 

잠깐 머리식힐 겸 이문제를 풀어봤는데 머리 식힐만한 문제가 아니었다.. 내가 제일 싫어하는 좋아하는 수학을 써야하는 문제였다... 일단 문제링크를 하단에 첨부한다.

 

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

1188번: 음식 평론가

 

문제를 풀다보니 분수로 접근하게 됐는데 이부분에서 막혀서 결국 다른 분들의 해답을 보게 되었다. 그런데 알고보니 굉장히 허무했다... 내 시간...! 내 머리가 내 시간을 가져가버렸따..

 

본론

문제 풀이방법을 설명하도록 하겠다.

소세지가 연결되어 있다고 생각하고 소세지 2개, 평론가 6명인 예제를 생각해보자. 

분수로 생각해보면 위의 그림의 모양을 띨 것이다. 그렇다면 잘라야하는 최소 개수는 4가 된다! 그러면 그 다음 예제인 소세지 3개, 평론가 4개인 경우도 그림으로 그려보자.

그림으로 그리면 위의 모습이 될 것이다. 3/4를 x개 만들어서 N의 값이 나오도록 하면 된다. 그렇다면 칼집은 x-1개가 된다. 결국 여기서 x는 분모의 값(M)이고, x-1은 M-1 임을 알 수 있다. 그런데 계산을 하려면 기약분수 형태가 되어야 한다. 기약분수가 되려면(분모가 나누어지지 않는 분수) 분모를 공약수로 나누어주면 된다. 따라서 M/(N과 M의 최대공약수) - 1의 값이 나온다. 이 공식을 계산하기 편하도록 분수 형태를 없애주기 위해 N과 M의 최대공약수를 양측에 곱하면 결과식은 M - N과 M의 최대공약수 라는 식이 도출된다. 정리하면 아래와 같다.

 

1. N/M 을 X개 만들어서 N의 값이 나오도록 하려면, X = M이 되며, 칼집의 값은 M-1이 됨
2. 기약분수 형태로 만들어주기 위해 분모(M)에 M과 N의 최대공약수를 곱함
3. 계산을 쉽게하기 위해 최대공약수를 곱하면 M - N과 M의 최대공약수 라는 식이 도출됨

 

결론

칼질 횟수는 M - (N과 M의 최대공약수)이다.

 

 

풀이한 코드

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        if(N%M == 0)    // N이 M으로 나누어 떨어지면 자를 필요 없다.
            System.out.println(0);
        else    // N이 M으로 나누어 떨어지지 않으면, 두 수의 최대공약수를 구해서 (M - 최대공약수)를 반환한다.
            System.out.println(M - BigInteger.valueOf(N).gcd(BigInteger.valueOf(M)).intValue());
    }
}

최대공약수를 구하는 메소드는 BigInteger에만 있어서 이를 이용했다.

 

느낀점

수학적으로 생각하는 버릇을 들여야겠다. 거의 다 풀어놓고 못알아내니 허무하고 아쉽다.