[1037] 약수

난이도: ★☆☆☆☆ • solved on: 2026-01-15

---

문제 요약

• 문제 유형: 수학, 약수 성질
• 요구사항: 어떤 수 (N)의 진짜 약수들(1과 (N) 제외)이 주어질 때, (N)을 구해야 한다.

---

사용 개념

1. 자료구조

   • 입력 순회(최솟값/최댓값 갱신)

2. 알고리즘/기법

   • 약수의 짝(pair) 성질 이용

3. 핵심 키워드

   • 약수 쌍(divisor pair), 최소/최대 약수

---

풀이 아이디어

왜 최소 약수 × 최대 약수 = N 이 되는가?

핵심은 약수는 항상 쌍으로 존재한다는 성질이다.

• 어떤 수 $N$에 대해 약수 $d$가 있으면, 항상 $N/d$도 약수이다.
• 따라서 약수들은 $(d, N/d)$ 형태의 짝으로 묶인다.
• 이때 각 짝의 곱은 항상 ($d \times (N/d) = N$) 이다.

---

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long max = Long.MIN_VALUE;
        long min = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            long temp = Long.parseLong(st.nextToken());
            if (temp > max) max = temp;
            if (temp < min) min = temp;
        }

        System.out.println(min * max);
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

---

어려웠던 점

• 왜 최소 약수와 최대 약수를 곱하면 원래 수 N이 되는지 직관적으로 이해가 안됐다. 하지만 테스트 케이스를 기준으로 규칙성을 찾아 이해는 안되지만 구현하니 됐다.
• “약수는 쌍으로 묶이고, 가장 작은 약수의 짝이 가장 큰 약수”라는 연결이 바로 떠오르지 않았다.

---

배운 점 및 팁

• 약수 문제는 대부분 짝(pair) 성질을 떠올리면 식이 단순해진다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1037
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 2501번 약수 구하기
  • 백준 - 9506번 약수들의 합

• 확장 문제 (GPT 추천) :

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 3036번 링