코드 복사/붙여넣기 하는 당신이 아름답습니다.

1188 : 음식 평론가

풀이

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-22 16:39

Read more posts by this author