0과 1의 쉼터

풀이 "백준 14939, 불 끄기"와 비슷하지만 행렬의 크기가 다른 문제다. 소스코드 #include #define min(a, b) a = 0 && ny >= 0 && nx < N && ny < N) temp[nx][ny] = (temp[nx][ny] == '1' ? '0' : '1'); } } int main(){ scanf("%d", &N); for (..

풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다. 우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다. N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다. 소스코드 #include #include #include #define min(a, b) a < b ? a : b char bulb[10][10], temp[10][10]; const char* lRow = "##########"; int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1}; ..

풀이 입력받은 비용들의 총 합을 구해주고, 비용별로 확보할 수 있는 메모리의 최댓값을 구해야 한다. 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

풀이 LCM을 구현하면 된다. 단, 결과가 너무 클 수 있으니 long long로 출력해주자. 소스코드 #include #define ll long long int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } ll lcm(int a, int b){ return (ll)a*b/gcd(a, b); } int main(){ int n, a, b; scanf("%d", &n); while (n--){ scanf("%d %d", &a, &b); printf("%lld\n", lcm(a, b)); } } 출처 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다..

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

풀이 1부터 N까지의 LCM을 N이하인 소수들의 곱들로 나누면 되는 문제다. N LCM facter result 1 1 1 1 2 2 2 1 3 6 2 1 4 12 2 * 3 2 5 60 2^2 * 3 2 6 60 2^2 * 3 * 5 2 7 420 2^2 * 3 * 5 * 7 2 8 840 2^3 * 3 * 5 * 7 4 9 2520 2^3 * 3^2 * 5 * 7 12 10 2520 2^3 * 3^2 * 5 * 7 12 1~N의 LCM을 구할 때, N이하인 소수들의 거듭제곱으로 구하고 이를, N이하의 소수들로 나누어야 하므로 차수가 2이상인 소수들의 곱이 답이 된다. 때문에, result는 N이하인 소수의 거듭제곱으로 구할 수 있다. 다음과 같은 표를 생각해보자. mol prime 4 2 8 2 9 ..