0과 1의 쉼터

풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 ..

풀이 입력받은 정수 n의 배수 중 1로만 이루어진 배수를 찾아 자릿수를 출력하면 되는 문제다. 간단하게 1부터 시작해서 n으로 나누어 떨어질때까지 숫자 뒤에 1씩 붙여주면 된다. 뒤에 숫자 1을 붙일 때 마다 자릿수를 한 개씩 증가시켜 주자. 소스코드 소스코드 보기 출처 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net

풀이 주어지는 나머지 M이 모든 case가 일치한다는 보장이 없다. 매번 새로운 피보나치 수열의 수들에 대해 M으로 나눈 나머지로 이루어진 수열을 구해야한다. 다행히도 문제에서 요구하는 수열에는 Pisano Period라는 규칙성이 존재한다. 즉, 모든 피보나치 수열의 수들에 대해 계산할 필요가 없다. 결국 주기에 따라 수열들의 수는 반복을 하기 때문이다. 우선, 아래의 예제 Pisano Period table을 살펴보자. 피보나치 수열들을 K번째 피보나치수로 나누었을 때 나머지들의 수열이다. 즉, Pisano period의 주기는 나머지가 {0, 1}이 나올때를 기준으로 이루어진다는 것을 알 수 있다. 0만 나오는 경우에는 성립하지 않는다. 나머지가 {0, 1}이 나올때까지 반복해주자. 어차피 입력되는..

풀이 부터 시작해 주어진 M, N에 관련된 조건에 맞게 두 자연수를 1씩 증가(이 때 k도 1씩 증가) 해야 한다. 증가한 두 자연수가 이 되기 전에 와 일치하면, 그때의 k를 출력하면 된다. 기본적인 로직은 아래와 같다. 단순히 (M, N, x, y)가 (39999, 40000, 39999, 40000) 으로 주어져도 LCM(39999, 40000) = 1,599,960,000 이기에 위의 방식대로 모든 수를 다 구하면 시간초과가 발생할 것이다. 난이도가 실버1로 낮은 편이고, 주어지는 수 또한 작은 수에 해당되기에 중국인의 나머지 정리를 사용하지 않고도 풀이할 수 있다. 아래와 같은 풀이 과정을 통해 접근이 가능하다. 구하고자 하는 k는 이 가 되기 위해 (x = y)가 아닌 이상 M, N의 배수에 ..

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