[C언어]백준(BOJ) 1037 - '약수'

#문제 분석

문제 링크 | https://www.acmicpc.net/problem/1037

1037번: 약수

 

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
...
(더 자세한 요건과 문제는 링크에서)

 

요약 | 어떤 수 N에 대한 진짜 약수의 갯수와 약수들이 주어졌을 때 N 구하기. 

 

---

 

#코드

 

해당 문제는 기본 개념으로 '약수'가 뭔지 희미하게만 알아도 충분히 풀 수 있기에 코드 작성을 위한 알고리즘으로 바로 넘어와 보겠습니다. 

 

해당 문제의 알고리즘을 정리했던 이미지를 캡쳐해 보았습니다.

 

저는 경우의 수가 몇 개 되지 않는 것 같아 switch문을 활용해 주었습니다.

크게 첫 번째는 입력 개수가 2개 이상인 경우와 두 번째는 입력 개수가 1개인 경우입니다. 

 

예시1 에서 보다시피 입력 수가 2개 이상인 경우에 가장 작은 수 X 가장 큰 수 = N(구하고자 하는 출력값)이 도출됩니다. 이는 문제 조건이었던 '진짜 약수'의 정의 덕분에 성립합니다.

 

예시2 역시 '진짜 약수'의 정의 덕에 입력된 약수 X 입력된 약수 = N (구하고자 하는 출력값)이 도출돕니다. 

 

알고리즘은 매우 쉽습니다. 다만 코테에서 주의해야 하는 점은 바로 조건들입니다. 이번 문제에서의 적용해야 하는 조건은 아래와 같습니다.

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

 -> 32비트는 8바이트로 int type의 할당 용량(4바이트)을 초과합니다. 이 조건을 보고 long long 자료형으로 바꿔주었고, printf에 출력할 때도 %lld 로 바꿔주었습니다. 

 

앞으로도 문제를 꼼꼼히 읽자고 다짐했습니다...

 

어쨌든,,, 코드는 아래와 같습니다. 

#include <stdio.h>

int main() {

    int div_num = 0; // 약수 갯수
    int divisors[51] = {0}; // 약수들
    long long N = 0; // 구하려는 N
    int i = 0; // 반복 인덱스
    int min, max; // 약수들 중 최대값, 최소값 저장

    scanf("%d", &div_num);

    for(i=0; i<div_num; i++) {
        scanf("%d", &divisors[i]);
    }

    switch (div_num)
    {
    case 0:
    break;
    
    case 1:
    N = divisors[0] * divisors[0];
    printf("%d", N);
    break;
    
    default:
    min = max = divisors[0]; 

    for(int i = 0; i < div_num - 1; i++) {
        if(min > divisors[i+1]) {
            min = divisors[i+1];
        }  
    }

    for(int i =0; i < div_num - 1; i++) {
        if(max < divisors[i+1]) {
            max = divisors[i+1];
        }
    }

    N = min * max;
    printf("%lld", N);
        break;
    }

return 0;

}