문제 89
고기만두
세종대학교 ICPC팀은 연습이 끝나면 춘향미엔에 가서 고기만두를 먹는다는 전설이 있다.
이곳에서 고기만두 한 접시를 시키면 고기만두 $6$개가 나온다.
$N$명이 고기만두를 먹으러 춘향미엔에 갔다. $N$명 모두가 남기지 않고 정확히 같은 개수의 고기만두를 먹으려면, 고기만두를 최소 몇 접시 시켜야 할까? 단, 배가 고프므로 최소 한 접시는 시켜야 한다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$
출력
첫 번째 줄에 필요한 고기만두 접시 수의 최솟값을 출력한다.
예제 입력 1
3
예제 출력 1
1
예제 입력 2
4
예제 출력 2
2
공식 해설
접시를 $x$개 주문하면 만두는 $6x$개이다. 모두 같은 수를 남김없이 먹으려면 $N\mid6x$여야 한다.
$g=\gcd(N,6)$이라 하면 $N/g$와 $6/g$는 서로소이므로 위 조건은 $N/g\mid x$와 동치이다. 따라서 가장 작은 양의 접시 수는
\[
\frac{N}{\gcd(N,6)}
\]
이다.
최대공약수를 구해 이 값을 출력한다. 두 수 중 하나가 상수 $6$이므로 시간복잡도와 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
C++에서는 <numeric>의 gcd를 사용하여 N / gcd(N, 6)을 출력한다.
C 구현
int로 유클리드 알고리즘을 구하고 N/gcd(N,6)을 출력한다. gcd의 두 번째 인수가 6이라 연산량이 작다. 원 위의 모든 위치를 시뮬레이션하지 않는다.
Python 구현
math.gcd(N,6)을 사용해 N // gcd를 출력한다. 별도 방문 배열이나 각도 실수 연산은 필요 없다.
Java 구현
두 int에 유클리드 알고리즘을 적용하고 N/g를 출력한다. Double 각도로 돌아오는 위치를 판정하지 않는다.
Rust 구현
u32 정수로 gcd(N,6)을 구하고 나눈다. 입력은 1000 이하라 큰 정수나 별도 원형 자료구조는 필요 없다.
JavaScript 구현
$N\le1\,000$이므로 Number 정수로 유클리드 호제법을 사용한다. JS 표준 라이브러리에는 gcd가 없지만 두 변수의 작은 반복문이면 충분하다.
let a = n, b = 6;
while (b !== 0) [a, b] = [b, a % b];
console.log(n / a);계산한 최대공약수는 $N$의 약수이므로 마지막 나눗셈은 정확한 정수이다. 접시 수를 하나씩 늘리거나 만두의 배분을 시뮬레이션하지 않는다.