백준 1188번 [음식 평론](C++)-yes6686- 티스토리

백준 문제 풀이: 1188 [음식 평론]

---

문제 링크: https://www.acmicpc.net/problem/1188

문제 설명:

음식의 길이가 n이고 m명의 평론가가 동일한 크기로 자르고 싶습니다. 음식의 길이를 균등하게 나누는 과정에서 나이프를 사용한 최소 횟수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int n, m;
    cin >> n >> m;
    int k = gcd(n, m); // 최대공약수 계산
    cout << k * (m / k - 1); // 나이프 사용 횟수 계산
}

---

코드 설명

• 핵심 알고리즘: 최대공약수를 이용해 최소 횟수를 계산합니다.
• 구현 세부사항:
  • 두 수 n과 m의 최대공약수 gcd를 구합니다.
  • 최대공약수로 나눠진 조각을 기준으로, 칼질 횟수는 m / gcd - 1과 같음을 이용합니다.
• 시간 복잡도: O(log(min(n, m))) (유클리드 호제법)

---

결과

주어진 음식 길이와 평론가의 수에 대해 최소 칼질 횟수를 계산하여 출력합니다. 최대공약수를 활용한 간결한 풀이입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!