해보자고

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

프로그래밍/C언어

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

초코맛동산 2024. 1. 25. 22:02

#문제 분석

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

 

1037번: 약수

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

www.acmicpc.net

 

양수 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;

}