[백준 1188번] 음식 평론가

문제 링크: 1188번 음식 평론가

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

 

풀이 과정보다, 풀이 과정을 떠올리는 과정을 먼저 설명해보면, 결국 어떻게 나누어지는지 실제로 몇 가지 예를 들어보는 편이 가장 빠른 것 같다. 적어도 민간인 머리를 가진 나에게는 말이다. 생긴 것부터 정수론 문제인 만큼, n > m일 때와 n < m일 때, 그리고 n % m == 0인지의 여부 등을 따져 몇 가지를 고려해보니 반례도 한 번에 고려할 수 있었다.

 

14라인

일단, 그냥 나누어주면 끝나는 경우에는 한 번도 자를 필요가 없다. 이는 빵이 사람의 배수인 것을 말하고, 물론 사람이 1명인 경우도 포함된다.

 

18라인

그리고 빵이 사람보다 많은 경우에는, 일단 나누지 않고 온전히 줄 수 있는 빵을 먼저 준 후에 빵을 나누어주면 된다.

 

22라인

이는 사람의 수가 빵의 개수의 배수인 경우이다.

빵이 5개, 사람이 20명인 경우를 생각해보자. 1명당 받아야 하는 빵의 양은 5/20 = 1/4이므로, 각 빵은 다음과 같이 나누어진다.

 

1번 빵: 1/4   1/4   1/4   1/4
2번 빵: 1/4   1/4   1/4   1/4
...
4번 빵: 1/4   1/4   1/4   1/4
→ 1인분이 5/20 = 4조각 → 칼질 4-1 = 3번

 

이를 조금 더 일반화해서 표현하면 아래와 같을 것이다.

빵이 pk개, 사람이 p개인 경우를 고려해보면, 1명 당 k만큼 받으면 된다. 곧, 각 빵마다 k등분해야하므로, 빵마다 칼질을 k-1번 한다.

 

27라인

서로소인 경우이다.

빵이 11개, 사람이 102명인 경우를 생각해보자. 1명당 받아야 하는 빵의 양은 11/102이므로, 각 빵은 다음과 같이 나누어진다.

 

01번 빵: 11/102   11/102   ...   11/102   3/102
02번 빵: 11/102   11/102   ...   11/102   3/102
...
20번 빵: 11/102   11/102   ...   11/102   3/102
→ 1인분이 11//102 = 9조각, 나머지 1조각 (총 9+1조각) → 칼질 9번

 

1인분짜리 조각은, n // m개 나온다. 하지만 m % n == 0인 위 경우와 달리, 나머지도 조각이 남는 것을 감안해야 한다.

 

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        System.out.println(get(n, m, 0));
    }

    static int get(int n, int m, int cnt) {
        if (n % m == 0) {
            return cnt;
        }
        
        if (n > m) {
            return get(n % m, m, cnt);
        }

        if (m % n == 0) {
            cnt += n * (m / n - 1);
            return cnt;
        }

        cnt += n * (m / n);
        m -= n * (m / n);
        return get(n, m, cnt);
    }
}