풀이
n과 m의 최대공약수를 이용해 문제에 접근해보자.
n과 m이 서로소인 경우, 서로소가 아닌 경우로 나눌 수 있다.
g = gcd(n, m)이라고 하자.
f(n, m)을 n과 m에 대한 답을 구하는 함수라고 하자.
f(n, m) = f(n/g, m/g) * g임은 자명하게 알 수 있다.
그러므로 g != 1인 경우의 답은 g = 1인 경우의 답을 알면 구할 수 있고
우린 모든 경우에 대해 답을 구할 수 있게 된다.
어떤 a, b에 대해서 gcd(a, b) = 1인 경우의 답이 어떻게 되는지 알아보자.
결론부터 말하면 a개의 소시지를 이어붙여서 정확히 b등분 하면 된다.
gcd(a, b) = 1일 때, d = a/b라고 두자.
gcd(a, d * (1...b-1))은 항상 1이므로 이어붙인 부분을 다시 자르는 일은 없다.
직선을 b-1번 잘라야 b개의 직선으로 나뉘는 것을 잊지 말자.
증명 끝.
따라서 답은 f(n/g, m/g) = f(a, b) = b-1이고 이를 정리하면
f(n, m) = f(n/g, m/g) * g = (b-1) * g = b*g - g = m - gcd(n, m)
∴ f(n, m) = m - gcd(n, m)
코드
#include <stdio.h>
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int main() {
int n, m;
scanf("%d %d", &n, &m);
printf("%d", m - gcd(n, m));
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이