백준 알고리즘 - 1037번 : 약수

백준 알고리즘 1037번 약수 문제입니다.

(참고 - https://www.acmicpc.net/problem/1037 )

코드 )

#include <stdio.h>

#include <stdlib.h>

int main() {

int cnt, i, j, result;

int *num = (int *)malloc(sizeof(int) * 50);

int *temp = (int *)malloc(sizeof(int) * 50);

scanf("%d", &cnt);

for(i = 0; i < cnt; i++) {

scanf("%d", &num[i]);

}

if(cnt == 1)

result = num[0]*num[0];

else {

for(i = 0; i < cnt; i++) {

for(j = 0; j < cnt-1; j++) {

if(num[j] < num[j+1]) {

temp[j] = num[j];

num[j] = num[j+1];

num[j+1] = temp[j];

}

}

}

result = num[0] * num[cnt-1];

}

printf("%d\n", result);

return 0;

}

- 이번에는 기본 stdio.h 외에 stdlib.h 를 추가해 사용해보았습니다.

int형 포인터를 사용하여 malloc을 이용해 메모리할당을 해줍니다. 

변수 cnt는 약수의 갯수이며, 약수의 갯수만큼 num배열에는 진짜 약수의 값을 입력받아 저장해줍니다.

만약 원래의 어떤 수 N의 약수의 갯수가 1개라면, N은 '그 약수의 제곱인 수' 라고 할 수 있습니다. 따라서 num에 입력받은 약수의 값을 제곱하여 N을 구해줍니다.

만약 약수의 갯수가 2이상이라면, 입력받은 num 배열의 값들을 전부 정렬해 준 뒤,

0번째의 값(약수의 가장 최소 값) 과 cnt-1번째의 값(약수의 가장 최대 값) 을 곱해주면 N의 값을 구해 줄 수 있습니다.

해당 문제는 약수란 무엇이고, 어떻게 구해야 하는 지가 포인트라고 할 수 있습니다.

따라서 약수중 최소값과 최대값을 곱해 준 값이 원래의 수 라는 것만 발견해낸다면 문제는 푼것이나 다름없다고 할 수 있습니다. 

정렬하는 과정은 프로그래머의 방법에 따라 다양할 수 있겠죠.

+Java)

import java.util.Arrays;

import java.util.Scanner;

public class algo1037 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int loop = sc.nextInt();

int[] arr = new int[loop];

for(int i=0; i<loop; i++) {

arr[i] = sc.nextInt();

}

if(loop == 1) {

System.out.println(arr[0] * arr[0]);

}

else {

Arrays.sort(arr);

int s = arr[0] * arr[loop-1];

System.out.println(s);

}

sc.close();

}

}