0과 1의 쉼터

풀이 8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다. 심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다. 때문에, 다음과 같은 규칙을 찾아 문제를 해결했다. N의 자릿수는 2, 3, 5, 7 이어야 한다. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다. 소스코드 #include #include int prime(int num){ int sq = sqrt(num); for (int i = 2; i

풀이 "백준 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

풀이 에라토스테네스의 체로 소수가 아닌 수들을 찾고, 입력받은 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..

풀이 "백준 2467, 용액"과 동일한 문제이다. 단, 입력되는 특성값이 항상 오름차순이라는 문구가 빠졌다. 정렬 후 탐색을 해주자. 소스코드 #include #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[rig..

풀이 특성값의 합이 기존에 구한 특성값의 합보다 작다고 항상 0에 가까운건 아니다. ex) -1 + 1 = 0, -10 + 1 = -9 때문에 특성값 합의 절대값을 이용해 구해야한다. 새로운 특성값 합의 절대값이 기존 특성값 합의 절대값보다 작을 때, 새로운 특성값의 합과, 두 용액의 특성값 또한 새로 담아주어야 한다. 소스코드 #include #include int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[right]; while (le..

풀이 "백준 11758, CCW"를 이용해 풀이했다. 벡터곱의 값은 두 벡터로 이루어지는 평행사변형의 넓이와 동일하므로, 벡터곱의 값을 반으로 나눈 값을 더해주면 된다. 기준점이 필요하기 때문에 처음에 입력받은 좌표를 기준점으로 했다. 소스코드 #include typedef struct{ double x, y; }Point; int main(){ int N; scanf("%d", &N); Point p[N]; for (int i = 0; i < N; i++) scanf("%lf %lf", &p[i].x, &p[i].y); double sum = 0; for (int i = 1; i < N; i++) sum += ((p[i-1].x - p[0].x)*(p[i].y - p[0].y) - (p[i-1].y -..

풀이 벡터곱을 이용해 P1P2에서 P3의 방향을 구할 수 있다. 소스코드 #include typedef struct{ int x, y; }Point; int main(){ Point p[3]; for (int i = 0; i 0 ? '1' : '0'); } 출처 및 참고자료 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 ..

풀이 "백준 9251, LCS"에서 LCS를 출력하기위해 사용했던 j, i값을 이용해 문자열이 동일한 경우를 Recursion방식으로 찾았다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; char str[2][1001]; void LCS(int j, int i){ if (dp[j][i]) if (str[0][i-1] == str[1][j-1]){ LCS(j-1, i-1); printf("%c", str[0][i-1]); }else dp[j-1][i] > dp[j][i-1] ? LCS(j-1, i) : LCS(j, i-1); } int main(){ scanf("%s %s", &str[0], &str[1]); int i, j; for..

풀이 첫째 줄에 입력받은 문자열의 각 문자와 둘째 줄에 입력받은 문자열간의 LCS를 구하는 방식으로 풀이했다. (j, i)번째에 각 문자열의 문자가 동일하다면, (j-1, i-1)번째의 LCS보다 1만큼 길다. 만약 문자가 같지않다면, 이전 LCS의 값 중 큰 값과 일치한다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; int main(){ char str[2][1001]; scanf("%s %s", &str[0], &str[1]); int i, j; for (i = 0; str[0][i]; i++) for (j = 0; str[1][j]; j++) if (str[0][i] == str[1][j]) dp[j+1][i+1] = dp[..

풀이 지문이 어마무시하게 길면서 Fermat’s little theorem에 대해 설명이 친절한 문제이다. 요점은 다음과 같다. M개의 N과 S에 대해 S*N^(MOD-2)의 합들을 MOD로 나눈 나머지를 구하면 된다. 단, N^(MOD-2)를 구하는 과정에서 수가 너무 커지므로 중간과정마다 MOD로 나누어줘야 한다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long sum = 0, N; int M, S; scanf("%d", &M); while (M--){ scanf("%d %d", &N, &S); long long temp = 1, k = MOD-2; while (k){ if (k & 1) temp = temp*N %MOD; k >>= 1; N ..