[ 백준 1037번 문제 ] 약수 - JAVA

이번 글에서는 백준 1037번 문제를 통해,
알고리즘 기본 문제 단골인 소수, 약수, 공배수 들 중 하나인 약수를 활용하여 문제를 풀어보자

문제 핵심

• 첫째 줄 : 약수의 개수
• 둘째 줄 : 약수들
• 구하려는 정수 : N
  • ( 풀이 과정에서는 구하려는 정수 N을 x라고 설명 )

풀이 과정

자연수 x을 구하려면 1과 x을 제외한 주어진 약수 중에서 선택해야 한다.

만약 이 때 조건과 같이 30의 약수를 차례대로 나열하면 [ 2, 3, 5, 6, 10, 15 ] 이다.

그렇다면 양쪽에서 순서대로 모두 짝지어서 곱한다면 x인 30을 구할 수 있다.

즉, 제일 큰 값과 작은 값을 구한 후 곱해주면 된다.

 

핵심 코드

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    if(num > max) {
        max = num;
    }
    if(num < min) {
        min = num;
    }
}

 

예외

9와 같은 약수는 1과 9는 제공되지 않기 때문에 3 숫자 하나만 주어진다.

이때 3의 제곱이 x가 되므로 첫째 줄이 1이라면 제곱해준다.

if(N == 1) {
    int num = Integer.parseInt(bufferedReader.readLine());
    stringBuilder.append(num * num);
}

 

단계적 풀이에서 브론즈 문제 수준으로
사실 비교적 아주 쉬운 문제이다.

이제는 마지막 브론즈 문제로 앞으로는 실버 상위부터 골드 문제가 다량으로 나올 예정이다.
지금까지 기초와 개념을 활용한다면 문제없이 풀 수 있을 것이다.

전체 코드

package org.example;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        if(N == 1) {
            int num = Integer.parseInt(bufferedReader.readLine());
            stringBuilder.append(num * num);
        } else {
            int max = 0;
            int min = Integer.MAX_VALUE;

            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(stringTokenizer.nextToken());
                if(num > max) {
                    max = num;
                }
                if(num < min) {
                    min = num;
                }
            }

            stringBuilder.append(max * min);
        }

        System.out.println(stringBuilder);

    }
}