문제 링크 www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 1) 각 수의 개수를 세줍니다. 2) 수 $i$마다, ($i$의 개수) * ($x - i$의 개수)를 정답에 더해줍니다. 3) 경우의 수가 두 번씩 중복되었으므로 정답을 2로 나눠준 뒤 출력합시다. 정답 코드 #include using namespace std; using ll = long long; ll n, x; map p; int ma..
문제 링크 www.acmicpc.net/problem/11693 11693번: n^m의 약수의 합 nm의 모든 약수의 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 $p_i$를 소수라 하고, $n$을 소인수 분해하여 $n = p_1^{m_1}p_2^{m_2}...p_k^{m_k}$라 합시다. 이때 약수의 합 $s$는 다음과 같습니다. $$\begin{eqnarray}s &=& (1+p_1^1+...+p_1^{m_1})(1+p_2^1+...+p_2^{m_2})...(1+p_k^1+...+p_k^{m_k}) \\ &=& \frac{p_1^{m_1+1}-1}{p_1-1}\times \frac{p_2^{m_2+1}-1}{p_2-1}\times ... \times \f..
문제 링크 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 $a^b$를 $c$로 나눈 나머지를 출력해야 합니다. 거듭제곱을 단순하게 구현하면 $\text{O}(b)$의 시간 복잡도가 나오므로 적절히 최적화를 해줘야 합니다. 1) 만약 $b$가 홀수라면, $a^b = a\cdot a^{b-1}$ 입니다. 2) 만약 $b$가 짝수라면, $a^b = a^{b/2}\cdot a^{b/2}$ 입니다. 이런 식으로 짝수일 때 $b$의 범위를 반씩 줄여나가면 $\text{O}(\log b)$의 복잡도로 거듭제곱을 구현할 수 있습니..
문제 링크 www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 풀이 1부터 시작해 0 또는 1을 붙여나가면서 $n$으로 나누어 떨어지는 수인지 확인합시다. 일반적으로 생각하면 수가 너무 크고, 경우의 수가 너무 많아 불가능합니다. 하지만 우리는 $n$으로 나누어 떨어지는지 여부만 알면 되기 때문에, 수 자체를 직접 저장하지 않고 그 수를 $n$으로 나눈 나머지 $r$만 저장해주면 됩니다. 어떤 수든 $(0 \leq r < n)$을 만족하므로 0, 1을 확장해가며 BFS를 돌려 정답을 찾을 수 있습니다. $r$에 $0$을 붙..
문제 링크 www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 나이브한 풀이는 $O(2^N)$ 완전탐색입니다. 물론 터집니다. 1) 주어진 입력을 절반으로 나누고, 각각 $2^{\frac{N}{2}}$ 의 완전 탐색을 돌려 모든 조합을 구합니다. 이렇게 구한 조합들을 $a, b$라 합시다. 2) $b$를 정렬하고, $a$의 모든 원소 $i$에 대해, $b$에서 $s - i$값을 가진 원소들을 찾아줍니다. upper b..