본문 바로가기

전체 글

 (277)
백준 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)!..
[USACO] 백준 5864 - Wifi Setup www.acmicpc.net/problem/5864 일직선상에 서있는 N(1 n >> a >> b; dp[0] = a; for (int i = 0; i > x; crd.push_back(x); } sort(crd.begin(), crd.end()); cout
백준 1744 - 수 묶기 https://www.acmicpc.net/problem/1744 두 수를 곱할 수 있을 때 주어진 수들의 최대 연산값을 구하라는 문제이다. 예시를 주의깊게 보도록 하자 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 그냥 $\Sigma arr$를 할 때보다 큰 수들을 곱한 후 더해주어서 최대 연산값을 이끌어내는 것을 볼 수 있다. 설명한 예시를 통해 가능한한 수들을 많이 곱하는 것이 답을 도출하는 길임을 알 수 있다. 그러면 주어진 수들을 모두 두개씩 곱해 다 더해버리면 되는 게 아닐까? 결코 아니다. 다음과 같은 테스트 케이..
백준 1976 - 여행가자 https://www.acmicpc.net/problem/1976 최대 200개의 도시 수가 인접행렬 형태로 주어진다. 문제에서 주어진 여행지들을 모두 여행할 수 있는지 판단할 것을 요구하고 있다. 즉 주어진 도시들이 연결되었는지를 판단하면 되므로 두가지의 풀이를 생각할 수 있는데 첫번째는 플로이드 워셜 알고리즘을 이용하여 쉽게 구하는 방법이고 두번째는 유니온 파인드를 이용해 각 정점들이 연결되어 있는지 판단하는 방법이다. 이 풀이에서는 유니온 파인드를 이용해보겠다. DisjointSet st(n); int loop; cin >> loop; for (int i = 0; i > connex; if (con..
백준 14720 - 우유 축제 https://www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다. 영학이는 우유 거리 www.acmicpc.net 영학이가 우유를 마시는 규칙에 따라 각 상태를 기억하는 방식으로 우유 가게를 순회하면 쉽게 풀 수 있다. 다음과 같은 배열을 구성해보..

티스토리툴바