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", &..

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

풀이 입력받은 컴퓨터 쌍을 서로 접근할 수 있도록 반대 쌍 또한 값을 설정해주었다. 그리고, 이전에 접속한 컴퓨터에서의 탐색(중복)을 막기 위해 컴퓨터 번호에 해당하는 num배열의 값을 증가시켰다. 소스코드 #include int arr[100][100], num[100], N, cnt; void dfs(int worm){ cnt++, num[worm] = 1; for (int i = 0; i < N; i++) if (arr[worm][i] && !num[i]) dfs(i); return; } int main(){ int line, x, y; scanf("%d %d", &N, &line); for (int i = 0; i < line; i++){ scanf("%d %d", &x, &y); arr[x-1]..

풀이 분 단위로 시간을 입력받아 24시로 표현하면 된다. 소스코드 #include int main(){ int H, M, time; scanf("%d %d %d", &H, &M, &time); printf("%d %d", (H+((M+time)/60))%24, (M+time)%60); } 출처 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net

풀이 키와 몸무게 둘다 큰 경우에만 cnt를 증가시켜준다. 소스코드 #include typedef struct{ int x, y; }Size; int main(){ int N; scanf("%d", &N); Size s[N]; for (int i = 0; i < N; i++) scanf("%d %d", &s[i].x, &s[i].y); for (int i = 0; i < N; i++){ int cnt = 0; for (int j = 0; j < N; j++) if (s[i].x < s[j].x && s[i].y < s[j].y) cnt++; printf("%d ", cnt + 1); } } 출처 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다...

소스코드 #include int main(){ int K, N, M; scanf("%d %d %d", &K, &N, &M); printf("%d", K*N > M ? K*N-M : 0); } 출처 10156번: 과자 첫 번째 줄에는 과자 한 개의 가격 K, 사려고 하는 과자의 개수 N, 현재 동수가 가진 돈 M이 각각 공백을 사이에 두고 주어진다. 단, K, N은 1,000 이하의 양의 정수이고, M은 10만 이하의 양의 정수이 www.acmicpc.net

풀이 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 수 N, M (N > M)을 입력받는다. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\ 나머지가 0이 될때의 N(몫)이 최대공약수이다. 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다. 소스코드 #include int euclidean_gcd(int n, int m){ return m ? euclidean_gcd(m, n%m) : n; } int main(){ int n, m; scanf("%d %d", &n, &m); int gcd = euclidean_gcd(n, m); printf("%d\n%d", gcd, n*m / gcd); } 출처 및 참고자료 ..