백준/수학 (35) 썸네일형 리스트형 백준 1188 - 음식 평론가 www.acmicpc.net/problem/1188 평론가들에게 같은 양의 소시지를 주기 위해 필요한 칼질 횟수의 최소를 구하는 문제이다. 알아야 할 것들 1. 가능한한 소시지는 칼질하지 않은 상태로 평론가들에게 주는게 최적해에 이를 수 있다. 즉 평론가들에게 칼질 없이 공평하게 소시지를 줄 수 있으면 답은 0이 된다. 2. 칼질을 해야 한다면 이 횟수를 줄이기 위해 소시지당 최적의 조각을 찾아야 한다. 여기에서 최적화된 소시지 조각을 찾는게 문제 해결의 핵심이다. 방법 우선 멀쩡한 소시지를 평가원에게 주고 남은 소시지와 평가원의 최대공약수를 찾는다. 남은 소시지를 최대 공약수로 나눠 몇묶음이 나올 수 있는지 regroup을 구한다. 묶인 소시지는 한개의 소시지로 친다. 그 다음 심사위원 수를 regro.. 백준 1629 - 곱셈 www.acmicpc.net/problem/1629 $A^{B} \mod C$ 를 빠르게 구해야 하는 문제이다. 단순하게 반복문을 통해 구한다고 하면 최대 2,147,483,647번 연산해야 하므로 이는 시간 내로 해결이 불가능하다. 따라서 해결을 위해서는 다른 방법이 필요하다. 이 문제 해결에 사용되는 알고리즘은 PS를 하는데 기본 소양이 되므로 그 방법을 잘 익히도록 한다. 예시로 $2^{1024}$를 구한다고 가정해보자. $2^{1024}$는 $2^{1024} = 4^{512}$ 으로 나타낼 수 있다. 그러면 $4^{512}$도 $4^{512} = 8^{256}$ 으로 나타낼 수 있다. 이처럼 지수를 절반씩 쪼개가며 제곱하면 $O(\log n)$의 시간복잡도로 빠르게 계산할 수 있다. 지수를 절반으.. 백준 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 ··· 4 5 6 7 다음
