엘릭시르제

문제 링크: https://www.acmicpc.net/problem/8483문제 풀이유리 등차수열의 내림 합, 정수론 $Ax + By > C$를 만족하는 위치에 모든 마천루가 사라졌다는 것은 $ Ax + By ≤ C$를 만족하는 위치에는 마천루가 남아있다는 뜻이다. 그리고 $x ≥ 0$, $y ≥ 0$인 정수 ($x$, $y$) 쌍의 마천루의 개수를 묻는 문제이다. 일단 $y$에 대해 식을 정리하면 $y \leq \frac{C-Ax}{B}$이고, 정수 값이어야 하니 $y$의 범위는 $0$부터 $\lfloor \frac{C-Ax}{B} \rfloor$까지. 즉 $\lfloor \frac{C-Ax}{B} \rfloor + 1$개다. $x$도 마찬가지로 $y$가 $0$ 이상의 값을 가지려면, $C - Ax ..

문제 링크: https://www.acmicpc.net/problem/28383문제 풀이소인수분해, 정수론 네 제곱수의 합의 가짓수를 구하는 방법은 Jacobi's four-square theorem를 이용하면 된다.간략하게 설명하면 $r_4(n)$이 $n$의 네 제곱수의 합의 가짓수를 구하는 함수인데,$n$이 홀수라면 $8\sigma(n)$를 구하면 되고, $n$이 짝수라면 $ n = 2^{k}m$으로 나타낼 때, $24\sigma(m)$을 구하면 된다.당연하겠지만 $\sigma(n)$를 구하기 위해서 소인수분해가 들어간다. $n = p_1^{q_1}p_2^{q_2}p_3^{q_3}\cdots p_k^{q_k}$으로 나타내면 $\prod_{i=1}^k \frac{p_i^{q_i + 1} - 1}{p_i..

1. 숫자 연결하기 (BOJ 1323)pigeonhole principle 언제 한번 순환소수 구할 때 나눗셈을 해본 적이 있다면 좋은 아이디어를 떠올릴 수 있다.1. 수를 계속 추가하면서(순환소수라면 0이었고, 이 문제에서는 N이다.) K로 나눠서 나머지를 알아낸다. 그후 그 나머지+N(여기선 문자열 연산이라 생각)을 다시 합쳐서 K로 나눈다.2. 계속 하다보면 언젠가 반복되었다.즉, 예제를 생각해보면 2%9=2 -> 22%9 -> 42%9 -> 62%9 -> ... 이런 식으로 계속 연산해준다. K로 나눈 나머지는 반드시 0~K-1이므로 비둘기집 원리에 따라 최대 K번 안에 반복된다. 같은 나머지가 나왔는데도 나머지가 0으로 안 나온다면 영원히 못 나누므로 -1을 출력하고 아니면 횟수를 출력하면 된다..

1. 동전 (BOJ 9084)dp, knapsack 동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다. 2. 겹치는 선분 (BOJ 1689)sweeping, sorting imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서..