문제 링크 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 어려워 보이지만 "어느 세 점도 일직선 위에 놓이지 않는다."라는 조건때문에 숨통이 트입니다. 이 조건만 보면 정말 반가워요.. 유니온 파인드를 이용해서 풀 수 있습니다. 주어진 선분의 양 끝점이 같은 집합이면 그 선분이 사이클을 만들게 됩니다. 그러니 이런 경우에 몇 번째 차례인지 출력하고 종료하면 됩니다. 정답 코드 #include #define mem(v, e) memset((v), ..
문제 링크 www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 풀이 이번에 새로 solved.ac 클래스 4에 추가된 문제입니다. 페르마 소정리와 모듈러 역원에 대해 친절하게 설명해줍니다. 정말 교육적인 문제예요.. 이제 문제는 $b^{x-2}$를 구하는 데 있습니다. $x$가 매우 크기 때문에 거듭제곱을 효율적으로 해야 합니다. 백준 1629 - 곱셈 문제와 같은 방식으로 거듭제곱을 빠르게 구해주도록 합시다. 정답 코드 #include #define TEST int _tt; cin >> _tt; while(_tt..
문제 링크 www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 $n$이 굉장히 큽니다. 여러 개의 식들을 하나의 행렬로 표현할 수 있습니다. $(a, b) \rightarrow (b, a+b)$가 되게끔 적절히 행렬로 표현해봅시다. 관련된 변수가 $a, b$ 두 가지니 2*2 행렬을 생각해볼 수 있습니다. $$\pmatrix{a & b}\pmatrix{ ? & ? \\ ? & ?} = \pmatrix{b & a+b}$$ $a, b$에 대한 식을 각각 세워봅시다. $$\begin{cases} a_{n+1} = 0\cdot a_{n} +..
문제 링크 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 $b$가 너무 큽니다. 백준 1629 - 곱셈 문제와 같은 테크닉을 이용해 거듭제곱 시간을 줄여줍시다. 행렬 곱셈의 경우 vector 타입의 곱셈 연산을 오버로딩해주면 편합니다. 1000으로 나눈 답을 출력해야 하는데, 초기 행렬 값이 1000이고 $b$=1인 경우를 주의해주세요. 입력받을 때도 1000으로 나눠주어야 합니다. 정답 코드 #include using namespace std; using ll =..
문제 링크 www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N이 주어진다.(1 ≤ N ≤ 1000) 둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M이 주어진다.(1 ≤ M ≤ 1 www.acmicpc.net 풀이 수가 매우 크기 때문에 $a, b$를 long long으로 표현할 수 없습니다. $a, b$를 소인수분해한 뒤, 겹치는 소인수를 모두 곱해주는 방식으로 정답을 구하면 됩니다. 근데 출력조건이 너무 불친절합니다. 9자리까지 출력해야 하는데, 만약 정답이 123,456이면 "123456"을, 1,000,123,456이면 leading zero를 포함하여 "00..
문제 링크 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..