Baekjoon3036: 링

링

1 초

128 MB

8087

6199

5724

78.637%

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

풀이1. 최대공약수 풀이

예제를 분석하다보면 백준 이전 문제의 최소공배수 문제와 같다는 것을 알 수 있다.

예제 1)

8 4 2 → 8 > 4 이고 둘의 최대 공배수는 8이다. 8/4 = 2, 8/8=1 → 2/1

8 4 2 → 8 > 2 이고 둘의 최대 공배수는 8이다. 8/2 = 4, 8/8=1 → 4/1

예제 2)

12 3 8 4

 → 12 > 3 이고 둘의 최대 공배수는 12이다. 12/3 = 4, 12/12=1 → 4/1

12 3 8 4 → 12 > 8 이고 둘의 최대 공배수는 24이다. 24/8 = 3, 24/12=2 → 3/2

12 3 8 4 → 12 > 4 이고 둘의 최대 공배수는 12이다. 12/4 = 3, 12/12=1 → 3/1

 

숫자 N을 입력 받으면 index[N-1] 크기의 배열을 만들고 처음 링을 따로 변수에 저장한다(=first).

first 값과 배열의 있는 각각의 값의 최소공배수(LCM)를 구한다.

(최소공배수÷배열의 값) / (최소공배수÷first)를 출력한다

이를 반복문으로 실행한다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int first = sc.nextInt(); //기준이 되는 링을 변수 저장
		int[] ring = new int[N-1]; //나머지는 배열 저장
		int LCM; //최소공배수 변수
		for(int i=0;i<N-1;i++) {
			ring[i]=sc.nextInt();
			int multiply = 1;
			while(true) { //최소공배수 찾기
				if(first*multiply%ring[i]==0) {
					LCM=first*multiply;
					break;
				}
				multiply++;
			}
			System.out.println(LCM/ring[i]+"/"+LCM/first);
		}
}}

 

 

풀이2. 최소공배수 풀이

최소공배수로 풀 수도 있고 최대공약수로 풀이할 수도 있다. 최소공배수를 first로 나누는 것이 아니라

first를 최대공약수로 나눠주면 된다

import java.util.*;
public class Main {
    static int GCD(int x, int y) {
		if(x==0)return y;
		return GCD(y%x,x);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int first = sc.nextInt();
		int[] ring = new int[N-1];
		for(int i=0;i<N-1;i++) {
			ring[i]=sc.nextInt();
			int gcd = GCD(first,ring[i]);
			System.out.println(first/gcd+"/"+ring[i]/gcd);
}}}