본문 바로가기

분류 전체보기735

[백준 2981] 검문 [C] 풀이 입력받은 N개의 수들이 M으로 나누었을 때, 나머지가 모두 동일하도록 하는 M을 구하는 문제이다. 단순하게 해결하기에는 정답 비율이 처참하다, 시간 초과를 생각해 효율적으로 M을 구하는 방법을 고안했다. N개의 수들을 다음과 같이 표현할 수 있다. arr[0] = M*q_0 + r arr[1] = M*q_1 + r arr[2] = M*q_2 + r " " arr[N-1] = M*q_N-1 + r M의 범위는 다음의 조건을 따른다. N >= 2일 때, 2번째 N보다 큰 M은 존재하지 않는다. (x = arr[1] - arr[0]) = M*(q_1 - q_0)이 성립하며, x의 약수 중에 N개의 수에 대해 만족하는 M이 존재한다. x의 약수가 아니더라도 M이 될 수 있으므로, x를 포함한 x의 약수를 .. 2021. 8. 28.
[백준 2023] 신기한 소수 [C] 풀이 8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다. 심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다. 때문에, 다음과 같은 규칙을 찾아 문제를 해결했다. N의 자릿수는 2, 3, 5, 7 이어야 한다. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다. 소스코드 #include #include int prime(int num){ int sq = sqrt(num); for (int i = 2; i 2021. 8. 27.
[백준 9020] 골드바흐의 추측 [C] 풀이 "백준 6588, 골드바흐의 추측"과 비슷한 문제이다. 단, 가능한 골드바흐 파티션이 여러 가지인 경우에 두 소수의 차이가 가장 작은 것을 출력해야 한다. N = 4인 경우에는 예외로 처리해줬다. 소스코드 #include #include #include #define MAX 10001 bool cNum[MAX]; int main(){ int sq = sqrt(MAX-1); for (int i = 2; i 2021. 8. 27.
[백준 1963] 소수 경로 [C] 풀이 네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, Queue에 담아주고, 자리수를 바꾸기 전의 수의 변환 횟수에 1을 더한 값을 자리수를 바꾼 후 숫자의 변환 횟수에 입력해주었다. 소스코드 #include #include #include #include #define MAX 10000 bool cNum[MAX]; int cnt[MAX], queue[MAX]; void bfs(int old, int pw){ int front = -1, rear = -1, n; cnt[queue[++rear] = old] = 0; while (front < rear){ if ((n = queue[++front]) == pw) return; for (int i = 0; .. 2021. 8. 26.
[백준 1990] 소수인팰림드롬 [C] 풀이 "백준 1747, 소수&팰림드롬"와 비슷한 문제다. 입력받은 a~b에 존재하는 팰림드롬 소수를 출력해주면된다. 단, 9,989,899 이후로 1e8까지는 팰림드롬 소수가 없기 때문에 범위에서 제한해주면 된다. 소스코드 #include #include #include #include #define MAX 9989900 bool cNum[MAX] = {0, 1}; int main(){ int sq = sqrt(MAX); for (int i = 2; i = MAX && (b = MAX-1); for (int i = a; i 2021. 8. 26.
[백준 1747] 소수&팰림드롬 [C] 풀이 에라토스테네스의 체로 소수가 아닌 수들을 찾고, 입력받은 N부터 소수인 수들중에 팰림드롬인지 확인해서 맞으면 해당 수를 출력하고 탐색을 종료하면 된다. 단, 98689 이후의 수들이 갖는 최소의 펠림드롬 소수는 1003001이므로 예외처리를 해주어야 한다. 소스코드 #include #include #include #include #define MAX 1000001 bool cNum[MAX] = {0, 1}; int main(){ int sq = sqrt(MAX); for (int i = 2; i 98689) puts("1003001"); else for (int i = N; i < MAX; i++) if (!cNum[i]){ char str[7]; sprintf(str, "%d", i); int l.. 2021. 8. 26.

티스토리툴바