유클리드 호제법8 [백준 1850] 최대공약수 (C++) https://www.acmicpc.net/problem/1850문제모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다. 출력첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 문제 풀이유클리드 호제법을 이용한 문제. 입력은 1의 개수로 주어지지만 A와 B 모두 1로만 이루어져 있기 때문에, 입력한 수들의 최대공약수를 구해주면 된다. 예를 들어 .. 2025. 3. 12. [백준 21870] 시철이가 사랑한 GCD (C++) 문제Q1. 사막에서 바늘을 찾는 방법은?A1. 대학원생을 시킨다.Q2. 신촌에서 자취방을 구하는 방법은?A2. 대학원생을 시킨다.연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와 GCD(Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.매물번호를 나타내는 정수 배열 S가 있다. (|S|=N, |S|는 S의 원소의 개수)배열 S의 원소를 왼쪽부터 ⌊|S|2⌋$\.. 2025. 3. 6. [백준 13412] 서로소 쌍 (C++) https://www.acmicpc.net/problem/13412문제두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다.어떤 자연수 N이 서로소인 두 자연수 A, B의 최소공배수라고 할 때, A, B로 가능한 숫자 쌍은 여러 개가 있을 수 있다. 예를 들어 N = 30인 경우 30을 최소공배수로 하는 서로소인 두 자연수로 가능한 숫자 쌍은 (1, 30), (2, 15), (3, 10), (5, 6)의 4가지가 있다.자연수 N이 주어질 때 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 출력하는 프로그램을 작성하시오. 입.. 2025. 2. 28. [백준 13241] 최소공배수 (C++) https://www.acmicpc.net/problem/13241문제정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.예:10은 5의 배수이다 (5*2 = 10)10은 10의 배수이다(10*1 = 10)6은 1의 배수이다(1*6 = 6)20은 1, 2, 4,5,10,20의 배수이다.다른 예:2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.10과 20의 최소공배수는 20이다.5와 3의 최소공배수는 15이다.당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.입력한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다.. 2024. 9. 24. [백준 1735] 분수 합 (C++) https://www.acmicpc.net/problem/1735문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 문제 풀이유클리드 호제법을 이용한 문제.두 분수 A/B + C/D를 계산하면 (AD+BC) / BD이다. 따라.. 2024. 7. 3. [백준 2485] 가로수 (C++) https://www.acmicpc.net/problem/2485문제직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.심어져 있는 가로수의 위치가 주어질 때,.. 2024. 6. 15. [백준 2436] 공약수 (C++) https://www.acmicpc.net/problem/2436 문제어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 .. 2024. 6. 3. [백준 11688] 최소공배수 찾기 (C++) https://www.acmicpc.net/problem/11688 11688번: 최소공배수 찾기 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. www.acmicpc.net 문제 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. 입력 첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012) 출력 첫째 줄에 c를 출력한다. 만약, 가능한 c가 없으면 -1을 출력한다. 문제 풀이 제목 그대로 최소공배수를 찾는.. 2024. 2. 29. 이전 1 다음