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

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

예제 입력 1 복사

30 42 70 35 90

예제 출력 1 복사

210

---

만만하게 봤는데 틀렸습니다가 뜨길래 당황했다.

dfs 종료 조건이 잘못됬었다.ㅠㅠ

 

5개의 수를 입력받은 후 dfs를 통해 모든 경우의 수를 조합한다.

5개 중 세개의 수를 골랐으면 세 개의 수의 최소공배수를 구한 후 결과값을 최신화한다.

틀린 부분은 cnt==3인걸 먼저 조사한 후 idx>5인 상황을 조사해야했는데 반대로 해서 틀렸었다.

 

아무튼 크게 어렵진 않지만, 유클리드 호제법, dfs가 섞인 문제였다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%A0%81%EC%96%B4%EB%8F%84%20%EB%8C%80%EB%B6%80%EB%B6%84%EC%9D%98%20%EB%B0%B0%EC%88%98(1145%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int p[6];
int visit[6];
int res = 987654321;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

void dfs(int idx, int cnt, int cur) {


	if (cnt == 3) {
		res = min(res, cur);
		return;
	}
	if (idx > 5) return;

	dfs(idx + 1, cnt, cur);

	dfs(idx + 1, cnt + 1, lcm(cur, p[idx]));

	return;
}

int main()
{
	for (int i = 1; i <= 5; i++)
		cin >> p[i];
	dfs(1, 0, 1);
	cout << res;
}