프로그래머스 Level 2 : N개의 최소공배수 C언어(시간단축)

▶문제 : 코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - N개의 최소공배수

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int arr[], size_t arr_len)
{
    int answer, num;

    answer = arr[0];//비교를 위해 먼저 arr[0]값을 대입
    for (int i = 1; i < arr_len; i++) {//i=1부터 반복
        num = answer;
        while (num % arr[i] != 0) {//num을 arr[i]로 나누어 떨어지면 num이 최소공배수
            num += answer;//num의 배수를 구하기 위해 num의 처음 값인 answer을 더해줌
        }
        answer = num;//최소공배수 대입
    }

    return answer;
}

 

▶해석

3과 4의 최소공배수를 구하는 방법은 많은데

4의 배수를 구하면서 3으로 나누어 떨어지는 방법을 이용하였다.

4의 배수는 4,8,12... 가 있는데 12%3이 0이므로 최소공배수는 12이다.

이때 배수를 구할 때 4+4=8 => 8+4=12 => 12+4=16 이런 식으로 구했다.

 

하지만 3, 4, 5 세 수의 최소공배수를 구하려면

3과 4의 최소공배수인 12를 변수에 저장하여

12와 5의 최소공배수를 구하였다.

 

코드를 보면 answer 변수는 최소공배수를 저장하는 변수이다.

비교를 위해 answer에 arr [0]부터 대입하여 반복문으로 arr [1]부터 비교하였다.

num은 answer의 배수를 구하는 변수이다.

 

while문으로 num을 arr [i]로 나누어 떨어질 때까지 num의 배수를 구해 최소공배수를 구한다.

num의 배수를 구할 땐 num의 처음 값인 answer을 num+=answer 해준다.

answer와 arr [i]의 최소공배수인 num을 구하면 answer에 대입하여 반복하면서 다음 값의 최소공배수를 구한다.

 

lcm이라고 구하는 방법이 있다고 하니 이 방법도 풀어봐야겠다.