| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 3406 | 1359 | 1188 | 45.292% |
문제
선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.
선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.
예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다.
소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)
출력
첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다.
접근
개인이 가져야 되는 소시지는 M/N 개임을 바로 알 수 있다.
처음엔 1개짜리 소시지를 M/N개와 남는 소시지로 몇 개 만들고
남는 것들을 잘 잘라서 합쳐보면 괜찮지 않을까 생각했는데,
최적화 할 수가 없어서 바로 다른 방법을 찾아보았다.
그래서 그냥 간단하게 앞에서부터 소시지를 잘라보았다.
몇 가지 경우를 적고 테스팅해보니 이것이 최적해임을 바로 알 수 있었다.
그래서 M개의 소시지를 하나의 긴 소시지라고 생각하고, 기본 칼질이 M번이라고 생각했다.(맨 뒤 포함)
근데 여기서 M/N 크기로 자르다가, 정수를 만나면 칼질을 하지 않아도 된다.
그렇다면 정수를 M/N의 배수들이 몇 번 만날까?
그것은 바로 N과 M의 최대 공약수이다!
풀이
유클리드 호제법으로 최대 공약수를 구해주면 끝난다.
50이 최대 크기라 그냥 브루트 포스로 구해도 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int GCD(int a, int b)
{
if (a % b == 0) return b;
return GCD(b, a % b);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
CIN2(N, M);
COUT(M - GCD(N, M));
return 0;
}