0과 1의 쉼터

풀이 "백준 6588, 골드바흐의 추측"과 비슷한 문제이다. 단, 가능한 골드바흐 파티션이 여러 가지인 경우에 두 소수의 차이가 가장 작은 것을 출력해야 한다. N = 4인 경우에는 예외로 처리해줬다. 소스코드 #include #include #include #define MAX 10001 bool cNum[MAX]; int main(){ int sq = sqrt(MAX-1); for (int i = 2; i

풀이 에라토스테네스의 채로 소수가 아닌 수들을 먼저 구한 후 풀이를 했다. 두 수의 합이 N과 같고, 두 수가 소수인경우에만 반복문을 종료해 답을 출력해주면 된다. 소스코드 #include #include #include #define MAX 1000001 int main(){ int sq = sqrt(MAX-1); bool not_prime[MAX] = {0,}; for (int i = 2; i

풀이 조건에 맞게 값을 넣어줄 수 있는 Binary Search Tree를 구현하는 문제이다. 소스코드 #include #include typedef struct node{ int data; struct node *left, *right; }*pNode; void postorder(pNode root){ if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d\n", root->data); } pNode make_tree(pNode root, int data){ if (root == NULL){ root = (pNode)malloc(sizeof(pNode)); root->data = data; root->left..

풀이 단지별로 bfs를 사용해 탐색하고, 방문한 곳을 0으로 만들어주었다. 단지내 집의 수를 main으로 반환해 complex에 담아주었고, Quick Sort로 정렬 후 출력해주었다. 소스코드 #include #include #define MAX 25 typedef struct{ int x, y; }Point; Point queue[MAX*MAX]; int graph[MAX][MAX], rear, N; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void push(int i, int j){ queue[rear].x = i; queue[rea..

풀이 "백준 7576, 토마토"에서 좌표축을 하나 추가해주면 된다. 소스코드 #include #define MAX 101 int box[MAX][MAX][MAX], M, N, H, rear; int dx[6] = {-1, 1}; int dy[6] = {0, 0, -1, 1}; int dz[6] = {0, 0, 0, 0, -1, 1}; typedef struct{ int x, y, z; }Queue; Queue q[MAX*MAX*MAX]; void push(int i, int j, int k){ q[rear].x = i; q[rear].y = j; q[rear++].z = k; } int bfs(int empty){ if (!empty) return 0; int x, y, z, px, py, pz, fro..

풀이 "백준 2178, 미로 탐색"과 풀이가 비슷하다. 단, 시작점이 여러개이다. 토마토의 여부를 입력받을 때, 익지않은 토마토의 개수와 익은 토마토의 개수를 미리 계산했다. 익지않은 토마토를 발견할 때마다 empty를 하나씩 감소하며, 탐색이 끝난 후 empty가 0보다 크면 모든 토마토가 익을 수 없는 상황이기 때문에 -1을 반환했다. #include #define MAX 1001 int box[MAX][MAX], M, N, rear; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct{ int x, y; }Queue; Queue q[MAX*MAX]; void push(int i, int j){ q[rear].x = i; q[rear++..

풀이 (0, 0)부터 범위를 초과하지 않고, 이동할 수 있는 공간이고, 방문한적 없는 곳을 탐색하면 된다. 다음에 이동할 좌표 (tx, ty)를 구조체 q에 저장하고 front, rear을 이용해 탐색을 진행했다. 소스코드 #include #include bool visited[100][100]; int graph[100][100], d[100][100]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct{ int x, y; }Queue; void bfs(int N, int M){ d[0][0] = visited[0][0] = 1; Queue q[N*M]; q[0].x = q[0].y = 0; int x, y, front = 0, rear..

풀이 가치가 n인 동전으로 k를 만드는 경우의 수는 k-n을 만드는 경우의 수와 같다. (단, k-n = 0의 경우의 수는 1로 설정) ex) n = 2, k 1 2 3 4 5 6 7 경우의 수 0 1 0 1 0 1 0 가치가 n1, n2인 동전으로 k를 만드는 경우의 수는 "k-n을 만드는 경우의 수 + n1으로 k를 만드는 경우의 수"와 같다. ex) n1 = 1, n2 = 2 k 1 2 3 4 5 6 7 8 9 10 n1 1 1 1 1 1 1 1 1 1 1 n2 2 2 3 3 4 4 5 5 6 이를 코드로 표현하면 다음과 같다. for (int i = 0; i < n; i++) for (int j = coin[i]; j

풀이 편의를 위해 합 또한 2차원 배열로 저장을 해주었다. 다음은 문제의 예제로 주어진 표에 대한 누적 합을 저장한 배열 sum이다. [x, y]가 의미하는 바는 [1, 1] 부터 [x, y]까지의 누적 합이다. 만약, [2, 3](초록색), [4, 4](노랑색) 구간의 합을 구할 때, [2, 3]을 기준으로 불필요한 누적 합인 [1, 4](=10), [4, 2](=24)을 빼주면 된다. 하지만, [1, 4]와 [4, 2]를 빼는 과정에서 공통된 누적 합(분홍색)을 두번 빼므로, [1, 2]를 더해주어야 한다. 정리하면 다음과 같다. // input :: 4 4 2 3 sum[x2][y2]- sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] // ex) [4, 4] -..

풀이 정답은 2의 K제곱들의 합이다. "백준 13731, A" 문제에서 2의 제곱을 구하는 방식을 이용해 풀이했다. 2의 K제곱(D)들의 합(sum_D)을 차수와 계수의 곱에 곱해주는 것을 반복하면 된다. 소스코드 #include #define MOD 1000000007 int main() { int N; scanf("%d", &N); long long result = 0, C, K; for (int i = 0; i < N; i++) { scanf("%d %d", &C, &K); long long DC = (C*K)%MOD, sum_D = 1, D = 2; K--; while (K) { if (K & 1) sum_D = sum_D*D %MOD; D = D*D %MOD; K /= 2; } result = ..