문제 https://www.acmicpc.net/problem/3955 3955번: 캔디 분배 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 www.acmicpc.net 설명 선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 (K × X + 1) 개를 구매하려고 한다. 사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 C개 들어있다 문제 조건을 식으로 나타내면 K x X + 1 = C x Y (X, Y는 자연수) 이다. 이 식을 베주 항등식으로 바꾸고 변수를 보기 편하게 바..
문제 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 설명 N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지게 해야 한다. 모든 경우의 수를 하나하나 따지면 수행시간이 O(\(N^{2}\)) 이지만 누적합을 사용하면 O(N) 으로 해결할 수 있다. LtoR 배열에는 배열 좌측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. RtoL 배열에는 배열 우측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. 최대공약수를..
문제 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 설명 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 먼저 K보다 작은 소수를 에라토스테네스의 체를 이용해 구한다. P가 구한 소수들에 나누어 떨어지는지 확인하고 하나라도 있다면 break를 하여 빠져나온다. boolean[] checked = new boolean..
문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 설명 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구해야 한다. \( \dfrac{A}{B} + \dfrac{C}{D} = \dfrac{A \times D + B \times C}{B \times D} \) 분수의 합을 계산하는 방법은 다음과 같다. 여기서 기약분수로 만들어야 하므로 최종 결과에서 분자와 분모의 최대공약수를 구하고 분자와 분모를 각각 구한 값으로 나눠주면 된다. int temp1 = A * D + B * C; int te..
유클리드 호제법 두 개의 자연수가 주어졌을 때, 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 두 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. gcd(a, b) = gcd(b, r) gcd(a, b, c) = gcd(gcd(a, b), c) a = 36, b = 28 36 % 28 = 8 gcd(36, 28) = gcd(28, 8) 28 % 8 = 4 gcd(28, 8) = gcd(8, 4) 8 % 4 = 0 gcd(8, 4) = gcd(4, 0) 따라서, 36과 28의 최대공약수는 4가 된다. ..
문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 설명 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 먼저 입력된 수보다 작거나 같은 소수를 구한다. 에라토스테네스의 체를 이용하면 쉽게 구할 수 있다. 소수인 수의 배수만 지우면 나머지는 소수가 된다는 방식이다. 나중에 연속된 소수의 합을 구하기 쉽게 소수인 수만 primeList에 저장해놓는다. boolean[] prime = new boolean[N + 1]; List primeList = new ArrayList(); // 소수는 false로 표시, 0..
에라토스테네스의 체 소수가 되는 수의 배수를 지우면 남은 건 소수가 된다. 아래는 위키백과에 나온 에라토스테네스의 체를 이용해 소수를 구하는 방법이다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 위의 그..
