0과 1의 쉼터

풀이 C(N, K)에 대해 N의 범위는 1 ~ 10, K의 범위는 0 ~ N이므로 단순 계산으로 풀이할 수 있다. C(N, K) = N! / (K! * (N - K)! N! = N * (N - 1) * (N - 2) * ... * 1 (N - K) ! = (N - K) * (N - K - 1) * (N - K - 2 ) * ... * 1 이때, N의 sub factorial과 K! 을 구해서 나누어주면 곱셈 횟수를 줄일 수 있다. ex) N = 5, K = 2 5 4 3 2 1 2 1 3 2 1 소스코드 소스코드 보기 출처 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net

풀이 두 좌표를 기준으로 반지름만큼의 원이 형성될 때 원의 둘레가 겹치는 좌표의 개수를 구하면 된다. 아래의 그림은 주어진 Test Case에 대한 시각화 자료이다. 만약 입력으로 주어지는 두 원이, 동일한 좌표와 반지름을 가진다면 '류재명'이 있을 수 있는 위치는 무한대이다. 두 원의 정보에 대한 입력을 struct Circle을 통해 입력받고, 두 원의 중심거리(d)와 두 원의 반지름의 차(diff_radius), 두 원의 반지름의 합(sum_radius)을 구해서 다음과 같은 비교를 통해 문제를 해결할 수 있다. 입력받은 두 원의 정보가 동일하다면 류재명이 있을 수 있는 위치는 무한대이다. d == sum_radius 이거나, d == diff_radius(아래 그림 참고)이면 한 접점에서만 만난다..

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

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

풀이 난이도에 비해 생각할 내용이 좀 많은 문제였다. 점수를 계산할 수들을 소수로 나누고 곱하는 과정을 통해 가장 큰 점수를 알아내는 문제이다. 즉, 입력받는 수들을 소인수분해하고, N개의 수들이 가장 큰 gcd값을 가지도록 소인수를 재분배하는 문제이다. 1e6까지의 78,498개의 소수들을 구하고, 입력받은 num에 대해 소인수분해를 하면서 소인수의 개수를 세주어야 한다. 다음의 예제를 보자. 8 = 2*2*2 24 = 2*2*2 *3 9 = 3*3 일때, N개의 수에 대해 2는 6개, 3은 3개가 존재한다. 이때 N = 3개의 수에 대해 각 수가 가져야할 인수들의 평균 개수는 2는 2개(6/N), 3은 1개(3/N)이므로, N개의 수들이 인수를 2*2*3으로 가질때가 가장 큰 gcd값이다. 문제에서 ..

풀이 euler_phi(x) = n/x가 성립하기 위해서는, n/x가 정수 이여야 한다. 즉, x는 n의 약수이어야 한다. n의 약수들을 모두 구한 후 오름차순으로 정렬해서 최소의 x를 찾아도 되고, 약수를 구해서 바로 계산을 해도된다. O(n^(1/2)) 만에 약수를 구하는 방법을 사용했다. 소스코드 #include #define min(a, b) a < b ? a : b int euler_phi(int n){ int euler = n; for (int p = 2; p*p