문제https://www.acmicpc.net/problem/9020풀이수학, 에라토스테네스의 채, 소수 판정 소수 판정에는 에라토스테네스의 채를 사용하여, 알고리즘 시작 전에 10000까지 소수를 판정해 둔다. 두 소수의 차이가 가장 적은 것을 출력해야 하므로, 시작 값(start)을 n / 2로 설정하여, 중앙에 가장 가깝도록 한다. start를 1씩 감소 시키면서, n - start가 소수라면 해당 값이 차이가 가장 적은 소수이므로 이를 출력하고 알고리즘을 중지한다. 처음에는 두 포인터로 문제를 해결하였지만, 위의 방법이 더 효율적이였다. 코드방법 1#include #include using namespace std;const int MAX = 4'000'001;bool prime[MAX];// 에..
문제https://www.acmicpc.net/problem/1065풀이수학, 브루트포스 알고리즘 입력되는 수는 1000 이하의 수이다. 100 미만의 수는 모두 한수를 이루기 때문에, 100 미만의 수가 들어온다면 N을 출력한다.0 ~ 9까지의 수는 그 자체로 등차수열이다.10 ~ 99까지의 수는 수열을 이루는 수가 2개이기 때문에 등차수열이다.100 이상의 수가 들어온다면 100부터 N까지 아래의 검사를 실시하여, 통과된 개수를 출력한다.현재 수의 각 자리수를 구한다. 연속된 자리수 사이의 차이가 일치한다면 한수이다. 코드#include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.t..
문제 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 풀이 수학, 우선순위 큐 [백준][C++] 2075: N번째 큰 수 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmic kantatatam.tistory.com 위의 문제와 약간 비슷하다. 위의 문제는 전체 수 중에서 N번째로 큰 수를 찾는 문제로, ..
문제 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..
문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다. 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서..
문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 수학, 브루트포스 알고리즘, 조합론, 백트래킹 사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다. void dfs(int index) { // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검..
문제 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 수학 N이 최대 10,000이므로 모든 순열을 구한다면 시간 초과에 메모리 초과이다. 주어진 순열의 바로 다음 순열을 구하는 방법은 다음과 같다. 순열의 가장 오른쪽부터 바로 왼쪽 원소가 자신보다 작은지 검사한다. 작다면 그 왼쪽 원소(기준)의 오른쪽 원소들 중 기준보다 큰 값 중 가장 작은 값을 가지는 인덱스를 찾는다. 인덱스와 기준의 원소를 맞바꾼다. 기준의 오른쪽 원소들을 오름차순으로 정렬한다. 만약 첫단계에서 알고리즘이 종료된 경우, 해당 순열은 사전순으로 마지막에 오는 순열인 경우로 -1을 출력한다. 코..
