[ 백준 1188 ] 음식 평론가 (C++) - 최대공약수

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 최대공약수를 구하는 문제이자 패턴 문제이다. 모든 소시지를 합쳐서 1개로 만들고 균일하게 자른다고 생각하면 된다. 이 때, 소시지를 합치는 자리를 칼질하는 경우만 카운팅을 안하면 된다.
2. 예제 2번 케이스에서 3 4 => 인당 3/4가 필요하다는 뜻이고, 이는 소세지 3개를 이어 붙여서 1개로 만든 다음에 4등분하면 된다는 뜻이다. 따라서 3번만 자르면 된다.
3. 다시 예제 1번 케이스를 보자 2 6 이 들어오고 인당 2/6이 필요하다. 이는 소세지 2개를 이어 붙여서 1개로 만든 다음에 6등분하면 된다는 뜻인데, 그러면, 총 5번의 칼질 중 1번의 칼질은 카운팅할 필요가 없다. 이는 최대공약수로 나타낼 수 있다.
4. 따라서 모든 칼질 횟수 - 최대 공약수 가 필요한 칼질 횟수가 된다.

---

⭐️ 정답 코드 및 설명

#include <iostream>

using namespace std;

int N, M;  // 소시지, 평론가

int gcd(int p, int q) {
    if (q == 0) return p;
    return gcd(q, p % q);
}

int main() {
    cin >> N >> M;

    cout << M - gcd(M, N);

    return 0;
}

---

🤔 문제 후기

문제풀이는 생각했는데, 최대공약수 구하는 방법을 까먹어서 고생했다... 결국 최대공약수를 구하는 공식은 인터넷에 검색해서 풀었는데, 최대공약수 최대공배수 구하는 알고리즘 자체는 나중에 외워두고 테스트를 보러 가야할 것 같다.