Baekjoon3036: 링

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

풀이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

from http://devyoseph.tistory.com/175 by ccl(A) rewrite - 2021-12-03 22:01:57