본문 바로가기

분류 전체보기735

[백준 5615] 아파트 임대 [C] 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.출력첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다... 2021. 8. 29.
[백준 11402] 이항 계수 4 [C] 풀이 Fermat’s little theorem을 기반으로 한 Lucas' theorem으로 풀이했다. Lucas' theorem는 다음과 같다. 쉽게, nCk를 M으로 나눈 나머지를 구하기 위해서는 N과 K를 M진 전개해 얻은 각 자릿수의 조합끼리 곱하고 M으로 나누면 된다. ex) input : 100 45 13 100 = 13*7 + 1*9 45 = 13*3 + 1*6 int result = 1; while (N || K){ result = result*nCk(N%M, K%M, M) %M; N /= M, K /= M; } nCk는 Fermat’s little theorem으로 구했다. 소스코드 #include int nCk(int N, int K, int M){ int A = 1, B = 1; fo.. 2021. 8. 28.
[백준 15791] 세진이의 미팅 [C] 풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 15791번: 세진이의 미팅 모태 솔로인 세진이는 이번에는 꼭 여자친구를 사귀어야겠다는 마음으.. 2021. 8. 28.
[백준 13977] 이항 계수와 쿼리 [C] 풀이 "백준 11401, 이항 계수 3"의 확장 문제이다. M개의 N과 K에 대해 이항 계수를 계산해야 하므로, 미리 4e6까지의 factorial과 역원을 구해주면 된다. 소스코드 #include #define ll long long #define MAX 4000001 const int MOD = 1e9+7; int A[MAX] = {1}, B[MAX]; int pow(ll a, int b){ ll result = 1; while (b){ if (b & 1) result = result*a %MOD; b >>= 1; a = a*a %MOD; } return result; } int main(){ for (ll i = 1; i < MAX; i++) A[i] = A[i-1]*i %MOD; B[MAX-1] .. 2021. 8. 28.
[백준 16134] 조합 (Combination)[C] 풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 16134번: 조합 (Combination) \(\begin{pmatrix}N\\R\end{p.. 2021. 8. 28.
[백준 11401] 이항 계수 3 [C] 풀이 MOD가 소수이기 때문에, A = N! - (N-K)!와 B = K!를 MOD로 나누며 구하고, Fermat’s little theorem를 이용해 ( A* B^(MOD-2) )%MOD를 구하면 된다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", .. 2021. 8. 28.

티스토리툴바