문제
첫 번째 링이 한 바퀴 회전할 때, 나머지 각 링이 몇 바퀴 도는지 기약분수로 출력하라.
입력
첫째 줄에 링의 수 N, 둘째 줄에 각 링의 반지름이 주어진다.
출력
2번째부터 N번째 링까지 회전수를 기약분수(a/b)로 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 12 3 8 | 4/1 3/2 |
풀이
첫 번째 링 반지름과 각 링 반지름의 비를 GCD로 약분하여 기약분수로 출력한다.
- 첫 번째 링의 반지름 F를 저장한다
- 각 링의 반지름 O에 대해 GCD(F, O)를 구한다
- F/GCD와 O/GCD를 분수 형태로 출력한다
핵심 아이디어: 첫 번째 링이 1바퀴 돌면 접촉 거리는 2πF이고, i번째 링은 2πF / 2πRi = F/Ri 바퀴 돈다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day470BOJ3036링 {
static int N, F, O;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
F = Integer.parseInt(st.nextToken());
for (int i = 1; i < N; i++) {
O = Integer.parseInt(st.nextToken());
int gcd = gcd(F, O);
sb.append(F / gcd).append('/').append(O / gcd).append('\n');
}
System.out.println(sb);
br.close();
}
static int gcd(int a, int b) {
int r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
}복잡도
- 시간: O(N * log R) - 각 링에 GCD 계산
- 공간: O(1)