0과 1의 쉼터

풀이 i번째 공이 잡을 수 있는 크기는 i번째 공보다 크기가 작고, 색상이 다른 공들의 합이기 때문에, 입력받은 공들을 공의 크기, 색별로 정렬을 해주었다. 출력순서는 입력순서와 동일해야 하므로, 정렬된 정보들에 대해 index별로 담아 줄 수 있는 배열들을 사용했다. for (int i = 0; i < N; i++){ scanf("%d %d", &b[i].color, &b[i].size); b[i].idx = i; } qsort(b, N, sizeof(Ball), compare); int sum_all = 0; for (int i = 0; i < N; i++){ int s = b[i].size, c = b[i].color, idx = b[i].idx; sum_all += s; same_color[c] ..

풀이 최악의 경우 모든 체스판의 정보가 1로만 이루어질 때, 시간초과가 발생하기 때문에, 효율적으로 풀이해야 한다. 모든 경우를 고려할 때 시간초과가 발생하는 이유 중 하나는 비숍이 규칙적으로 놓일 수 있는 공간에 대해 생각하지 않기 때문이다. 다음처럼 비숍을 놓는 경우를 생각해보자 즉, 흰색과 회색에 놓일 수 있는 비숍으로 구분해서 탐색한다면 규칙적으로 놓일 수 있는 공간대로 탐색할 수 있다. 입력받은 체스판의 정보에 대해 만약 놓을 수 없는 공간이라면 다음 공간으로 넘어가면 된다. 소스코드 #include #include bool board[11][11], l[19], r[19]; int N, result[2]; void bishop(int row, int col, int cnt, int color)..

풀이 입력받은 비용들의 총 합을 구해주고, 비용별로 확보할 수 있는 메모리의 최댓값을 구해야 한다. for (int i = 0; i = c[i]; cost--) dp[cost] = max(dp[cost], dp[cost-c[i]] + m[i]); 그 후 입력받은 M만큼의 메모리 이상을 확보하는 비용을 찾아 출력하면 된다. 소스코드 #include #define MAX 101 #define max(a, b) a > b ? a : b int c[MAX], m[MAX], dp[10001]; int main(){ int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) scanf("%d", &..

풀이 a*b = gcd(a,b)*lcm(a,b)이므로 양변의 약수가 같다는 점을 이용해 풀이했다. 소스코드 #include int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int main(){ int A, B, a, b; scanf("%d %d", &A, &B); B /= A; for (int i = 1; i*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..

풀이 단지별로 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..