문제 2725번: 보이는 점의 개수 첫째 줄에 테스트 케이스의 개수 C(1
유클리드 호제법
문제 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 풀이 수학, 유클리드 호제법 좌석을 분수로 생각한다. 반지름이 i이면서 j번째 좌석은 i / j로 표현한다. i1 / j1과 i2 / j2가 기약분수로 표현했을 때, 같은 값을 가진다면, 한 좌석은 다른 좌석을 가리게 된다. D1부터 D2까지의 좌석을 기약분수로 나타냈을 때, 중복되는 경우 답에 추가하지 않는다. 코드 #include using namespace std; // 좌석을 분수로 표현 bool nums[2001][2001]; int gcd(int ..
문제 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 수학, 유클리드 호제법 소시지를 일자로 이어붙였을 때, M등분 하기 위해서는 길이가 N / M이 되도록 잘라야 한다. 이를 위해선 총 M - 1번 잘라야 한다. 소시지는 일자로 이어붙인 상태이므로, 이미 잘려진 부분이 존재한다. 이 잘려있는 부분이 M - 1번 자른 부분과 동일한 경우, 해당 부분은 자른 횟수에서 제외해야 한다. 이 동일한 부분은 (N과 M의 최대공약수 - 1)개 이다. N이 5, M이 15인 경우, 소시지 하나는 3조각으로 나눠진다. 이 때, 조각 하나의 길이는 1/3이다. 총 잘려지는 횟수는 14번 이며, 이 중 겹치는 부분은 4번이다..
문제 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 풀이 수학, 유클리드 호제법 입력받은 최대공약수를 A, 최소공배수를 B, 구해야 하는 수를 x, y라고 하면 다음이 성립한다. x % A = 0, y % A = 0 (x * y) / A = B N을 x를 A로 나눈 몫이라고 하면 다음이 성립한다. x = N * A 위 식을 (x * y) / A = B에 대입하면 다음의 결과를 얻을 수 있다. x = N * A, y = B / N y는 자연수 이므로, B / N은 나누어 떨어져야 한다. 그러므로, N은 B의 ..
문제 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 유클리드 호제법, 수학 완전 탐색으로 하면 시간초과가 발생한다. 주어진 정수 A를 M으로 나눈 나머지가 R이라면 다음을 만족한다. R = A - (A / M) * M 여기서 A는 배열로 주이지므로 다음이 만족한다. R = A[0] - (A[0] / M) * M R = A[1] - (A[1] / M) * M ... R = A[N - 1] - (A[N - 1] / M) * M 문제에서 R이 같은 값이므로 다음이 만족한다. A[1] - A[0] = (A[1] / M - A..
문제 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 풀이 유클리드 호제법 S에서 일정한 간격으로 이동할 때, 모든 A에 도달해야 한다. 즉, 간격이 모든 A와의 차이의 공약수여야만 한다. 이 간격 중 최댓값이므로, 최대공약수가 정답이다. 코드 #include using namespace std; vector diffs; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % ..
문제 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 유클리드 호제법 모든 나무를 같은 간격으로 심으려면, 현재 심어져 있는 가로수 사이의 간격의 최소공배수만큼을 간격으로 설정하고 심으면 된다. // 가로수 사이의 간격의 최소공배수를 구한다. int GCD = nums[1] - nums[0]; for (int i = 1; i < nums.size() - 1; ++i) { GCD = gcd(GCD, nums[i + 1] - nums[i]); } 첫 가로수와 마지막 가로수 사이의 거리를 range라고..
문제 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 유클리드 호제법 회전하는 바퀴는 반지름 / (첫 번째 링과 i 번째 링의 반지름의 gcd) 로 구할 수 있다. 코드 #include using namespace std; int nums[100]; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } int main() { ios_base::sync_with_stdio(0..
문제 풀이 유클리드 호제법 간단한 유클리드 호제법 문제이다. 아래는 a, b의 최대공약수를 반환하는 유클리드 호제법 함수이다. int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 문제에서 주어진 분수를 먼저 통분하여 합을 계산한다. 합한 분자와 분모의 최대공약수를 구하여 각각에 나누면 기약 분수가 된다. 코드 #include using namespace std; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b..
