[백준 1145] 적어도 대부분의 배수

www.acmicpc.net/problem/1145

1145번: 적어도 대부분의 배수

백트래킹과 최소 공배수를 사용했다.

숫자가 5개라서 백트래킹을 돌렸다. 숫자 5개 중 3개를 선택하여 최소 공배수를 구한 후 가장 작은 값을 리턴한다.

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int res = 1000000;
int arr[5];
vector<int> selected;
int gcd(int a, int b)
{
  while (b)
  {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int lcm(int a, int b)
{
  return a / gcd(a, b) * b;
}

int getLcmThree(int a, int b, int c)
{
  return lcm(lcm(a, b), c);
}

void DFS(int idx, int cnt)
{
  if (cnt == 3)
  {
    int result = getLcmThree(selected[0], selected[1], selected[2]);
    res = min(res, result);
    return;
  }

  for (int i = idx; i < 5; i++)
  {
    selected.push_back(arr[i]);
    DFS(i + 1, cnt + 1);
    selected.pop_back();
  }
}
int main(void)
{
  for (int i = 0; i < 5; i++)
  {
    scanf("%d", &arr[i]);
  }

  DFS(0, 0);

  printf("%d\n", res);
  return 0;
}