페르마의 소정리와 분할 정복을 이용한 거듭제곱을 이용한 풀이입니다. #include #include using namespace std; int n, k; int divider = 1'000'000'007; long long int mul(long long int a, long long int b, long long int divider) { long long int ans = 1; while (b > 0) { if (b % 2 != 0) { ans *= a; ans %= divider; } a *= a; a %= divider; b /= 2; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; ..

백준 1003번은 기초적인 동적 계획법(DP, Dynamic programming) 문제입니다. 시간제한이 0.25초로 매우 빡빡한 편이라서 시간복잡도 O(n)으로 풀어야 해결 가능합니다. 다음 소스는 문제에서 주어진 $N$번째 피보나치 수를 구하는 C++ 함수입니다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이와같이 재귀적으로 N번째 피보나치 숫자를 구했을때 0과 1이 각각 몇번씩 return되는지 구하는 문제인데, $fib(n)$ 을 $n$번째 피보나치 숫자를 반환..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 백트래킹 구현시 항상 search()함수를 void 타입으로 구현했는데, int형으로 수정되어 최초해가 나오면 바로 모든 search()함..