기타등등/알고리즘 기록

[JAVA]백준 1037번 - 약수

CodeJB 2021. 2. 18. 01:24

서론

약수 문제 중 기본적인 문제이다.(solved.ac : 실버5 문제)

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

 

예제입력 / 예제출력

2

4 2              /          8

문제 풀이

- 우리가 구해야하는 N을 24라고 가정 하고 24의 약수를 나열해보면 1,2,3,4,6,8,12,24이다.

- 여기서 진짜 약수는 1과 24를 제외한 것이므로 2,3,4,6,8,12이다.

- 기본 상식이긴 하지만 규칙성을 잘 들여다보자(습관을 기르자)

- 양 끝의 값을 곱하면 N이 만들어진다.

- 코드상으로는 min과 max값을 구하여 곱하는게 편하므로 min값 구하는 함수와 max값 구하는 함수를 작성한다.

- 그리고 곱하면 N이 쉽게 만들어진다.

소스 코드

public class Main {
	public static void main(String[] args) {
		int SIZE;
		int max = 0,min = 0;
		int array[];
		int tmp;
		
		Scanner sc = new Scanner(System.in);
		SIZE = sc.nextInt();
		array = new int[SIZE];
		
		for(int i =0; i < array.length; i++) {
			array[i] = sc.nextInt();
		}
		
		max = array[0];
		min = array[0];
		
		for(int i =0; i < array.length; i++) {
			if(max < array[i]) {
				max = array[i];
			}		
			if(min > array[i]) {
				min = array[i];
			}
		}	
		System.out.println(max*min);	
	}
}

출력

문제로부터 얻어간 것

- 문제에는 "진짜 약수"라는 낯선 단어와 몇 가지 조건들이 있어서 자칫 어렵게 생각할 수 있지만, 종이에 그려보면 상당히 간단한 문제라는 것을 알 수 있다. 즉, 쫄지 말자

느낀점

사실 이런 문제는 너무 간단하다. 코드에 익숙하지 않은 사람이라면 min max에서 고민을 할 수 있을 것 같다. min max를 스스로 생각 못했다면 해결할 때까지 공부해보는게 좋을 것 같다.