백준/수학 (28) 썸네일형 리스트형 백준 10250 - ACM 호텔 www.acmicpc.net/problem/10250 문제에서 손님이 아랫층이면서 엘리베이터에 가까운 순으로 타는 것을 선호한다는 것을 알 수 있고 첫번째 예시를 도식화 하면 6 ... 5 ... 4 10 ... 3 9 ... 2 8 ... 1 7 ... 표와 같이 10번 위치인 402호에 들어가게 된다. 따라서 해당 손님이 들어갈 위치를 탐색하여 그 위치의 층과 호수를 계산해주면 된다. 전체코드 더보기 #include int main() { using std::cout; using std::cin; int n; cin >> n; int h, w, m; while (n--) { int sonnom(1); cin >> h >> w >> m; while (m - h > 0) { m -= h; ++sonnom.. 백준 10422 - 괄호 www.acmicpc.net/problem/10422 짝이 맞는 괄호의 개수는 카탈란 수의 잘 알려진(Well Known) 예시 중 하나이다. 카탈란 수에 대해 자세한 정보는 이 글에 있으며 $\binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{(n + 1)!n!}$ 다음과 같이 3개의 식으로 사용할 수 있다. 이 문제에서는 1,000,000,007로 나눈 나머지를 구해야 하므로 페르마의 소정리를 활용하기 위해 3번째 식을 이용했다. 주의 사항은 n쌍이 아니라 n개가 입력으로 주어지므로 괄호의 개수가 홀수개일 때는 괄호 짝이 절대 만들어지지 않는다는 점과 짝수개가 주어지면 이를 괄호의 짝 개수로 치환하기 위해 2.. 백준 13977 - 이항 계수와 쿼리 www.acmicpc.net/problem/13977 최대 10만 개의 쿼리에 대해 $\binom{n}{r} \ mod \ 10^9 + 7$ 을 구해야 하는 문제이다. N과 K는 400만 이하이기 때문에 이항 계수 DP나 일반적인 반복문 연산으로는 제한 메모리/시간 내로 10만개의 쿼리를 처리할 수 없다. 알아야 할 것 이 문제를 해결하기 위해선 페르마의 소정리를 이용해야 한다. 페르마의 소정리 : 소수 p가 있고 정수 a가 p의 배수가 아닐 때 다음이 성립한다. $a^{p} \equiv a \ (mod \ p)$ 페르마의 소정리를 통해 문제에서 요구하는 것을 빠르게 계산할 수 있다. 방법 일단 이항계수를 제곱식으로 바꾸면 다음과 같이 된다. $\binom{n}{r} = \frac{n!}{(n - r)!.. 이전 1 ··· 3 4 5 6 다음
