0과 1의 쉼터

풀이 "백준 6588, 골드바흐의 추측" 코드를 이용해 풀이했다. 단, 골드바흐의 추측은 짝수인 N에 대해 해당하기 때문에, 입력받은 N이 홀수인 경우 2, 3을, 짝수인 경우 2, 2를 먼저 출력해준 후 출력해준 수 만큼 빼준 N값에 대해 골드바흐의 추측을 사용해 풀이할 수 있다. 단, 8인 경우에는 2, 2, 2, 2이기 때문에 따로 써주거나 더 안정적인 골드바흐의 추측 알고리즘을 사용하면 된다. 소스코드 #include #include #include #define MAX 1000001 bool Cnum[MAX]; int main(){ int sq = sqrt(MAX); for (int i = 2; i

풀이 "백준 2470, 두 용액"의 응용 문제이다. 세 개의 특성값을 비교해야 하므로, 맨 왼쪽부터 기준이 되는 idx번째 특성값과, idx+1 ~ N-1의 특성값을 더해 0에 가장 가까운 용액을 만들어내는 특성값을 찾으면 된다. 단, 세 개 특성값의 최댓/최솟값이 int 범위를 벗어나므로, llabs()를 사용하고, 연산의 범위를 long long으로 선언했다. 소스코드 #include #include #define ll long long 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++) ..

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

풀이 건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다. W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다. 좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다. 단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다. 소스코드 #include #include #include #define max(a, b) a > b ? a : b int D[1001], N, check[1001]; bool O[1001][1001]; int construction(int c){ if (check[c] != -1) return c..

풀이 스도쿠를 완성시키고, 81자리의 수가 제일 작은 경우를 출력하면 되는 문제이다. Backtracking방식으로 스도쿠에 넣어줄 수 있는 작은 수 부터 탐색하면서, 만약 81번째 자리에 도달했다면 가장 작은 81자리의 수를 완성시킨 것이기 때문에 출력을 해주고 중단을 해줘야한다. 소스코드 #include int arr[9][9], print = 1; int check(int x, int y, int val){ for (int i = 0; i < 9; i++) if (arr[x][i] == val || arr[i][y] == val) return 0; x = (x/3)*3; y = (y/3)*3; for (int i = x; i < x+3; i++) for (int j = y; j < y+3; j++)..

풀이 연속된 수들의 부분합이기 때문에 Two Pointers로 쉽게 구현할 수 있다. start, end가 가르키는 배열의 합들이 S이상이면 최소 길이를 구해야 하며, 만약 sum이 S보다 작으면 end+1번째 요소를 더해주고, 그렇지 않다면 start번째 요소를 빼주는 방식으로 풀이했다. 소스코드 #include #define min(a, b) a < b ? a : b int main(){ int arr[100000], N, S, start = 0, end = 0; scanf("%d %d %d", &N, &S, &arr[0]); for (int i = 1; i < N; i++) scanf("%d", &arr[i]); int cnt = 1e5, sum = arr[0]; while (start = S) c..

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

풀이 16까지 1의 분포는 다음과 같다. N N의 2진수 1의 개수 1 1 1 2 1 0 2 3 1 1 4 4 1 0 0 5 5 1 0 1 7 6 1 1 0 9 7 1 1 1 12 8 1 0 0 0 13 9 1 0 0 1 15 10 1 0 1 0 17 11 1 0 1 1 20 12 1 1 0 0 22 13 1 1 0 1 25 14 1 1 1 0 28 15 1 1 1 1 32 16 1 0 0 0 0 33 2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다. 때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다. 완전히 반복되지 않은 구간에서의 1의 개수는, 2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수..