문제 링크 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..
문제 링크 www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 오일러 파이함수 $\phi(n)$를 구현하는 문제입니다. 어떤 수 $n$의 소인수 개수를 $m$개라 합시다. $$\begin{eqnarray}\phi(n) &=& n\prod_{p|n}(1-\dfrac{1}{p}) \\ &=& n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_{m}})\end{eqnarray}$$ 식의 앞에서부터 차례대로 전개하는 방식으로 구현하시면 됩니다. 정답 코드 #inc..
문제 링크 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 1) 아직 방문한 적 없는 칸에서 dfs를 돌려 갈 수 있는 곳까지 간 후, 인구수의 평균을 구해줍시다. 2) 그 칸에서 다시 한번 dfs를 돌려 각 나라의 인구수를 1에서 구한 평균값으로 바꿔줍니다. 3) 더이상 인구수의 변화가 없을 때까지 반복해주면 됩니다. 정답 코드 #include #define TEST int _tt; cin >> _tt; while(_tt--) #defi..
문제 링크 www.acmicpc.net/problem/20936 20936번: 우선순위 계산기 국렬이는 두 번씩이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 이대로라면 죽을 때까지 계산기를 우려먹을 생각이고, 당신은 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계 www.acmicpc.net 풀이 우선순위 큐를 이용한 구현 문제입니다. 사실 복잡한 구현 문제라 이해하기 쉽게 쓰기 힘들어 보여 귀찮아서 안 쓰려했는데.. 그래도 써야죠... 역시 알고리즘 문제는 푸는 것보다 설명하는 게 더 힘듭니다.. 전체적인 풀이 1) $X_1\ Op_1\ X_2\ Op_2\ X_3\ Op_3\ ...\ Op_{n-1}\ X_n$ 꼴의 수식이 공백 없이 주어집니다. 이를 적절히 처리하여 $X$와 $Op$를..
문제 링크 www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 기본적인 최소 스패닝 트리 문제입니다. 코스트가 $c$이상인 간선만 모아 최소 스패닝 트리를 만들어줍시다..