문제 링크 www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 풀이 문제를 해결하기에 다음과 같은 어려움이 있습니다. 1) 모든 순열을 고려해봐야 하는데 $O(N!)$이라 경우의 수가 너무 많습니다. 2) 순열을 합친 큰 정수가 커도 너무 큽니다. 최대 750자리 수입니다. 수가 너무 큰데?? 2번 문제부터 해결해봅시다. 사실 우리는 정확한 수를 알고 있을 필요가 없습니다. 결국 알고 싶은 사실은 어떤 수 $x$가 $k$로 나누어 떨어지는지입니다. 이를 백준 8111 - 0과 1 문제와 같은 방식으로 ..
문제 링크 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 =..