유클리드 호제법 (6) 썸네일형 리스트형 백준 14476번 [최대공약수 하나 빼기](C++)-yes6686- 티스토리 백준 문제 풀이: 14476 [최대공약수 하나 빼기]문제 링크: https://www.acmicpc.net/problem/14476문제 설명:n개의 정수 배열이 주어졌을 때, 배열에서 하나의 수를 제거했을 때 나머지 숫자들의 최대공약수를 구합니다. 그리고 제거된 숫자를 함께 출력합니다. 제거된 숫자가 최대공약수를 유지하지 못하는 경우는 제외합니다.문제 해결 코드#include #include using namespace std;int arr[1000001];int larr[1000001];int rarr[1000001];int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int main() { ios::sync_with_stdio(false); c.. 백준 2436번 [공약수](C++)-yes6686- 티스토리 백준 문제 풀이: 2436 [공약수]문제 링크: https://www.acmicpc.net/problem/2436문제 설명:두 정수 a와 b가 주어질 때, a는 두 수의 최대공약수(GCD), b는 최소공배수(LCM)입니다. 이러한 조건을 만족하는 두 수를 찾고, 두 수를 출력합니다. 여러 쌍이 있을 경우 두 수의 합이 가장 작은 쌍을 출력합니다.문제 해결 코드#include #include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}int lcm(long long int a, long long int b) { return (a * b) / gcd(a, b);}int arr[100001];int main().. 백준 1188번 [음식 평론](C++)-yes6686- 티스토리 백준 문제 풀이: 1188 [음식 평론]문제 링크: https://www.acmicpc.net/problem/1188문제 설명:음식의 길이가 n이고 m명의 평론가가 동일한 크기로 자르고 싶습니다. 음식의 길이를 균등하게 나누는 과정에서 나이프를 사용한 최소 횟수를 구하는 문제입니다.문제 해결 코드#include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}int main() { int n, m; cin >> n >> m; int k = gcd(n, m); // 최대공약수 계산 cout 코드 설명핵심 알고리즘: 최대공약수를 이용해 최소 횟수를 계산합니다.구현 세부사항:두 수 n과 m의 최대공약.. 백준 2485번 [가로수](C++)-yes6686- 티스토리 백준 문제 풀이: 2485 [가로수]문제 링크: https://www.acmicpc.net/problem/2485문제 설명:직선 도로에 여러 가로수가 일정하지 않은 간격으로 심어져 있습니다. 추가로 심어야 하는 가로수의 최소 개수를 구하는 문제입니다. 새로 심는 가로수는 기존의 간격을 일정하게 나누는 위치에만 심을 수 있습니다.문제 해결 코드#include #include using namespace std;int arr[100001];// 유클리드 호제법을 사용하여 최대공약수 계산int gcd(int a, int b) { int c; while (b) { c = a % b; a = b; b = c; } return a;}int main() { .. 백준 2981번 [검문](C++)-yes6686- 티스토리 백준 문제 풀이: 2981 [검문]문제 링크: https://www.acmicpc.net/problem/2981문제 설명:n개의 숫자가 주어질 때, 이를 m으로 나눴을 때 모두 같은 나머지를 가지는 m의 가능한 값을 오름차순으로 출력하는 문제입니다. 여기서 m은 1보다 커야 합니다.문제 해결 코드#include #include #include using namespace std;int arr[101];set s;// 최대공약수 계산 함수int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; .. 백준 2609번 [최대공약수와 최소공배수](C++)-yes6686- 티스토리 백준 문제 풀이: 2609 [최대공약수와 최소공배수]문제 링크: https://www.acmicpc.net/problem/2609문제 설명:두 자연수가 주어질 때, 두 수의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.문제 해결 코드#include using namespace std;int main() { int a, b; cin >> a >> b; // 최대공약수를 구하기 위한 범위 설정 int len = (a > b) ? b : a; int maxGCD = 1; for (int i = 1; i 코드 설명핵심 알고리즘: 최대공약수는 두 수를 나누어 떨어뜨릴 수 있는 가장 큰 수를 의미하며, 최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.구현 세부사.. 이전 1 다음
