[백준] 5618번: 공약수(수학)

https://www.acmicpc.net/problem/5618

5618번: 공약수

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bf.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for(int i=0; i<n; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		
		for(int i=1; i<=arr[0]; i++) {
			int count = 0;
			
			// 주어진 자연수의 공약수 찾기 
			for(int j=0; j<n; j++) {
				if(arr[j] % i == 0)
					count ++;
			}
			
			// 자연수 n개가 모두 i로 나누어떨어질때
			if(count == n)
				System.out.println(i);
		}
		
		
		bf.close();
	}

}

풀이

알고리즘을 안하다 보니 간단한 문제도 풀이가 바로 떠오르지가 않았다 ...

문제에서 자연수의 갯수가 2개 혹은 3개라고 해서 좀 생각했던 것 같다.

자연수를 입력받고, 정렬한 뒤 가장 작은 수까지 반복해서 공약수를 찾아준다.

공약수를 찾는거는 i가 1부터 가장 작은수까지 반복해가면서, 주어진 자연수와 나누어떨어질때 count값을 증가시키고,

count 값과 주어진 자연수의 갯수 n의 값이 일치하면 i값은 공약수이므로 출력해준다.