어떤 문제인가?

어떤 수의 약수가 모두 주어졌을 때, 어떤 수를 구하는 문제.

않이;; 이걸 왜 못함?

내가 빡통가리라는 걸 깨닫게 해준 문제 중 하나다.
내가 저지른 시행착오는 다음과 같다.

1. 뜬금없이 최소공배수를 구하려고 했다.

문제를 제대로 이해를 안한 탓일까. 내 머리속에서 든 생각은

아니 ㅋㅋ 그냥 다 곱하면 되는거 아님?

생각해보니 문제가 그렇게 단순하진 않을거라 생각했고, 최소공배수를 이용해야겠다는 생각까지 들었다. 호기롭게 유클리드 호제법을 이용해서 풀어보려고 했지만 당연히 될 리가.

2. 아; N=1일때 생각을 못했네;

그러고 보니 3만 들어가면 1, 3, 9로 제곱수의 꼴을 띄게 된다. 똑같이 딱 하나의 진짜 약수만 가지면 그렇게 될 거라 생각해 조건문을 달아서 다시 했다.
당연하지만 근본적인 문제가 해결이 안 됐는데 풀릴 리가?

3. 아 ㅋㅋㅋ '모든' 약수였어??

이때서야 모든 이라는 조건이 눈에 보였다. 그 동안 일부 약수만 가지고 뻘짓을 하고 있었다.
가운데를 기준으로 대칭되는 위치에 있는(예컨대, 1, 2, 3, 4, 6, 12에서 2, 6은 대칭되는 위치에 존재) 수를 곱하면 원래 수가 나온다는 것을 이용했다.

아 근데 이거 정렬이 안되어있지. 🤔
어차피 주어지는 데이터 수는 최대 1,000개라 선택 정렬로 정렬 후 풀었다.

다른 사람들은 어떻게 풀었나

어떻게 풀긴. 나보다 더 똑똑한 방법으로 다들 푸셨지.

# include <stdio.h>
int main(){
    int N,k,m=0,b=1000001;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&k);
        if(k>m) m=k;
        if(k<b) b=k;
    }
    printf("%d",m*b);
    return 0;
}

fin님 소스

• https://www.acmicpc.net/source/17240311

정렬조차 필요 없었다는 것에 놀랐다. 그저 최대/최솟값만 구하고 곱하면 끝난댄다. 아오 ㅋㅋㅋㅋ