0과 1의 쉼터

풀이 LCM을 구현하면 된다. 단, 결과가 너무 클 수 있으니 long long로 출력해주자. 소스코드 #include #define ll long long int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } ll lcm(int a, int b){ return (ll)a*b/gcd(a, b); } int main(){ int n, a, b; scanf("%d", &n); while (n--){ scanf("%d %d", &a, &b); printf("%lld\n", lcm(a, b)); } } 출처 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다..

풀이 a*b = gcd(a,b)*lcm(a,b)이므로 양변의 약수가 같다는 점을 이용해 풀이했다. 소스코드 #include int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int main(){ int A, B, a, b; scanf("%d %d", &A, &B); B /= A; for (int i = 1; i*i

풀이 gcd(x, y) = gcd(x-y, y)임을 이용해 풀이했다. A < B일때, gcd(A+N, B+N) = gcd(A+N, B-A)이므로, B-A의 약수를 이용해야 한다. 1~ B-A범위를 모두 탐색하면 시간초과가 발생하므로 다른 방법을 생각해야된다. 위의 예시에서 알 수 있듯이, 시작값(X)을 기준으로 X+N이 B-A로 나누어 떨어질 때 X~(X+B-A)구간에서 가장 작은 LCM값을 가진다는 점을 알 수 있다. X+N이 B-A로 나누어 떨어진다는 것은, B-A의 약수로도 나누어 떨어지는 것을 의미한다. 따라서, A가 B-A의 약수로 나누어 떨어지지 않을 때, N번째 수를 생성 후 LCM을 계산해 가장 작은 N값을 구하면 된다. 소스코드 #include #define ll long long int..

풀이 입력받은 N개의 수들이 M으로 나누었을 때, 나머지가 모두 동일하도록 하는 M을 구하는 문제이다. 단순하게 해결하기에는 정답 비율이 처참하다, 시간 초과를 생각해 효율적으로 M을 구하는 방법을 고안했다. N개의 수들을 다음과 같이 표현할 수 있다. arr[0] = M*q_0 + r arr[1] = M*q_1 + r arr[2] = M*q_2 + r " " arr[N-1] = M*q_N-1 + r M의 범위는 다음의 조건을 따른다. N >= 2일 때, 2번째 N보다 큰 M은 존재하지 않는다. (x = arr[1] - arr[0]) = M*(q_1 - q_0)이 성립하며, x의 약수 중에 N개의 수에 대해 만족하는 M이 존재한다. x의 약수가 아니더라도 M이 될 수 있으므로, x를 포함한 x의 약수를 ..

풀이 마지막 예제에서 힌트를 얻었다. 입력된 두 정수의 최대공약수 만큼 1을 출력해주면 된다. 소스코드 #include #define LL long long LL GCD(LL a, LL b){ return b ? GCD(b, a%b) : a; } int main(){ LL A, B; scanf("%lld %lld", &A, &B); LL i = GCD(A, B); while (i--) putchar('1'); } 출처 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net

풀이 입력받은 두 분수를 통분하고, 분자와 분모의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int A, B, a, b; scanf("%d %d %d %d", &A, &B, &a, &b); int AA = A*b + a*B, BB = B*b; int gcd = GCD(AA, BB); printf("%d %d\n", AA/gcd, BB/gcd); } 출처 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net

풀이 처음에 입력받은 링의 반지름과 이후에 입력받은 반지름의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int N, first_r, r; scanf("%d %d", &N, &first_r); while (-1 + N--){ scanf("%d", &r); int gcd = GCD(first_r, r); printf("%d/%d\n", first_r/gcd, r/gcd); } } 출처 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 ..

풀이 모든 쌍의 GCD를 구해서 합해주면 된다. 단, 최악의 경우 1,000,000 * 99 * 98 * 97 *... * 3 * 2 *1 의 수가 나올 수 있으니 long long 자료형의 변수에 합을 담아주어야 한다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int t, n, arr[100]; scanf("%d", &t); while (t--){ scanf("%d", &n); long long gcd_sum = 0; for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < n-1; i++) for (int j = 1 + i; j < n..

풀이 두 수의 곱을 최대공약수로 나누면 최소공배수이다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int T, A, B; scanf("%d", &T); while (T--){ scanf("%d %d", &A, &B); printf("%d\n", A*B / GCD(A, B)); } } 출처 및 참고자료 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net [백준 2609] 최대공약수와 최소공배수 [C..

풀이 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 수 N, M (N > M)을 입력받는다. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\ 나머지가 0이 될때의 N(몫)이 최대공약수이다. 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다. 소스코드 #include int euclidean_gcd(int n, int m){ return m ? euclidean_gcd(m, n%m) : n; } int main(){ int n, m; scanf("%d %d", &n, &m); int gcd = euclidean_gcd(n, m); printf("%d\n%d", gcd, n*m / gcd); } 출처 및 참고자료 ..