0과 1의 쉼터

풀이 n명에 대해서 각각 dfs을 해 만들어진 팀의 학생 수 만큼 전체에서 빼면 된다. 중복을 방지하기 위해, 팀을 짜기 시작한 경우(visited[0])와 탐색이 끝난 경우(visited[1])로 확인을 해주었다. 이전에 만난적 없는 번호이면 짝을 찾아가고, 만난적 있는 짝일 때, 그 짝의 탐색이 끝나지 않은 경우라면 순환이 가능한 즉 팀이 만들어 질 수 있다. 순환점을 발견하기 전 까지 재 탐색을 하며 개수를 세주고, 마지막에 자기 자신을 세어 주면 된다. 소스코드 #include #include #include #define MAX 100001 bool visited[2][MAX]; int arr[MAX], N, cnt; void dfs(int num, int depth){ if (!depth){ ..

풀이 최악의 경우 모든 체스판의 정보가 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의 부 배열에 대한 누적 합을 계산 후 정렬해주고, upper/lower bound로 가능한 경우를 계산해주면 된다. 단, 가능한 경우가 없을 수 있으니 left = diff) right = mid - 1; else left = mid + 1; mid = (left+right) / 2; }while (left

풀이 6번 줄의 실행 횟수에 따른 결과는 다음과 같다. i j sum 1 1 2 3 4 5 6 7 8 9 10 11 12 12 2 1 3 5 7 9 11 6 3 1 4 7 10 4 4 1 5 9 3 5 1 6 11 3 6 1 7 2 7 1 8 2 8 1 9 2 9 1 10 2 10 1 11 2 11 1 12 2 12 1 1 일반적으로 1~n까지의 수에 대해서 sum += (n-1)/i + 1이 성립한다. 하지만 시간초과가 발생하므로 모든 수에 대해 확인하지 않고, n의 약수에 대해서만 확인하는 방법이 필요했다. n의 약수(prime)에 대응하는 개수(temp)는 다음과 같이 구할 수 있다. for (int i = 2, temp; i < n; i = temp+1) temp = (n-1) / ((n-1)/i..

풀이 M명의 평론가들은 1개의 소시지에 대해 N/M만큼 가질 때, 모두 동일한 양을 가질 수 있다. 이는 M - gcd(N, M)으로 표현할 수 있다. 소스코드 #include int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int main(){ int N, M; scanf("%d %d", &N, &M); printf("%d", M - gcd(N, M)); } 출처 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net

풀이 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

풀이 입력된 대문자 알파벳의 아스키코드 값을 이용해, 한 번이라도 방문한 적 없는 경우에만 탐색해 최대의 칸 수를 구하면 된다. 소스코드 #include #include char arr[20][20]; bool visited[26]; int R, C, result; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; void BT(int x, int y, int cnt){ cnt > result && (result = cnt); for (int i = 0; i = 0 && ny >= 0 && nx < R && ny < C){ int idx = arr[nx][ny] - 65; if ..

풀이 gcd(x, y) = gcd(x-y, y)임을 이용해 풀이했다. A < B일때, gcd(A+N, B+N) = gcd(A+N, B-A)이므로, B-A의 약수를 이용해야 한다. 1~ B-A범위를 모두 탐색하면 시간초과가 발생하므로 다른 방법을 생각해야된다. 위의 예시에서 알 수 있듯이, 시작값(X)을 기준으로 X+N이 B-A로 나누어 떨어질 때 X~(X+B-A)구간에서 가장 작은 LCM값을 가진다는 점을 알 수 있다. X+N이 B-A로 나누어 떨어진다는 것은, B-A의 약수로도 나누어 떨어지는 것을 의미한다. 따라서, A가 B-A의 약수로 나누어 떨어지지 않을 때, N번째 수를 생성 후 LCM을 계산해 가장 작은 N값을 구하면 된다. 소스코드 #include #define ll long long int..

풀이 N이하 소수들의 가장 큰 거듭제곱들을 곱하고, 2^32로 나눈 나머지를 출력해주면 된다. 소스코드 #include #include #define MAX 100000001 bool cNum[MAX]; int main(){ for (int i = 2; i*i < MAX; i++) if (!cNum[i]) for (int j = 2*i; j < MAX; j += i) cNum[j] = true; int n; scanf("%d", &n); long long result = 1; for (int i = 2; i < MAX; i++) if (!cNum[i]){ long long temp = 1; while (temp*i