[백준 5347] LCM [C]
풀이 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사이에는 공백이 하나 이상 있다. 두 수는 백만보다..
2021. 9. 2.
[백준 11414] LCM [C]
풀이 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..
2021. 8. 31.
[백준 1850] 최대공약수 [C]
풀이 마지막 예제에서 힌트를 얻었다. 입력된 두 정수의 최대공약수 만큼 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
2021. 8. 3.
[백준 1735] 분수 합 [C]
풀이 입력받은 두 분수를 통분하고, 분자와 분모의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #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
2021. 8. 3.
