최소공배수2 [백준 1145] 적어도 대부분의 배수 www.acmicpc.net/problem/1145 1145번: 적어도 대부분의 배수 첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다. www.acmicpc.net 백트래킹과 최소 공배수를 사용했다. 숫자가 5개라서 백트래킹을 돌렸다. 숫자 5개 중 3개를 선택하여 최소 공배수를 구한 후 가장 작은 값을 리턴한다. #include #include #include using namespace std; int res = 1000000; int arr[5]; vector 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.. 2020. 12. 21. [백준 6064] 카잉 달력 www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 수학 문제이다. 어렵게 접근하면 한없이 어려워지지만 x를 고정하고 y값을 변화시킨다고 생각하면 쉽다. -1이 나오는 경우는 에 해당하는 마지막 k번째 해를 넘어갈 때인데 k는 m과 n의 최소 공배수이다. ++ 최소 공배수 구하기 a와 b의 최소 공배수는 a * b / gcd(a,b)이다. gcd는 유클리드 호제법을 사용하여 구해주면 된다. 정리하는 김에 코드를 간단히 적어본다. int gcd(int a, int b.. 2020. 12. 18. 이전 1 다음