알고리즘

문제 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..

문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 구현, 시뮬레이션 현재 order에서 움직일 기어들을 찾아서 방향에 맞게 회전시켜야 한다. 현재 order 기어의 오른쪽 기어들과 왼쪽 기어들을 나눠서 생각한다. // 현재 기어의 오른쪽 기어들 탐색 for (int current_gear = order_gear + 1; current_gear < 4; ++current_gear) { // 현재 기어와 현재 기어 바로 왼쪽 기어의 상태를 비교 if (gear[current_gear - 1][2] !=..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 각 칸에 대해서 연합을 이룰 수 있는지 확인하기 위해, 각 칸의 상하좌우를 탐색하여 연합을 만든다. 연합은 시작 칸과 인접한 칸에서만 이루어지는게 아니라, 연합이 이루어진 칸에서도 인접한 칸을 비교하여 조건에 맞으면 연합이 이루어진다. 그러므로 각 칸을 bfs로 탐색하면서 연합을 이루는 칸이 어느 칸인지 탐색한다. 연합 벡터의 수가 2이상이라면, 인구 이동이 가능한 상태이므로 인구 이동을 실시한다. 이를..

문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 구현, 시뮬레이션 주사위의 각 면을 나눠서 생각하고, 현재 주사위의 아래쪽(D), 오른쪽(R), 앞쪽(F)에 해당하는 주사위 면을 설정하여 해결하였다. 각 면의 인덱스를 0, 1, 2, 3, 4, 5라고 하면 처음 상태에서 D는 0, R은 2, F는 4이다. 주사위를 4방향으로 움직이면 D, R, F는 밑의 코드처럼 변한다. // 주사위를 4방향으로 굴렸을 때, 아래, 오른쪽, 앞쪽의 주..