DP(11)
-
백준 1354번, 무한 수열 2 풀이
문제 백준 1354번 풀이 문제는 $ A_{n} $을 구하는 것입니다. $ A_{i} $에 대한 점화식이 문제에 나와 있으니 재귀적으로 풀어봅시다. 피보나치 수열과 마찬가지로 비슷한 값의 중복 연산을 피하기 위해 DP를 사용해야 합니다. 이 문제의 경우 항 $ i $가 불연속적이고 매우 크므로, map을 사용해야 메모리 초과를 피할 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; unordered_map mp; ll n, p, q, x, y; ull ..
2020.11.23 -
백준 1737번, Pibonacci 풀이
문제 백준 1737번 풀이 기본적인 피보나치 문제도 DP이기 때문에, DP를 사용하는 문제임에는 쉽게 알 수 있습니다. 다만, 소수점 오차 때문에 dp table을 잡기가 조금 애매합니다. 소수점 오차를 줄이기 위해서 $ n $에서 뺄 1의 개수와 $ \pi $의 개수를 기록하여 dp table을 채우면 될 것 같습니다. $ dp[i][j] = f(n - i - \pi j) $라고 두고 재귀 함수로 풀었습니다. (단, $ f $는 Pibonacci 함수) 소스코드 #include using namespace std; typedef unsigned long long ull; ull MOD = 1000000000000000000; ull dp[1001][1001]; long double n; ull solv..
2020.11.01 -
백준 1226번, BOI 2008 4번, 국회 풀이
문제 백준 1226번 풀이 솔직히 문제 번역본이 그렇게 좋은 것 같진 않습니다. $ N $개의 정당 중 $ K $개의 정당을 뽑아서 연합을 만들 수 있습니다. ($ A_{i} $: $ i $번째 정당의 인원수) 이 연합에 속한 정당의 인원들의 합이 전체 정당의 인원수($ \sum_{i=1}^n A_{i} $)의 절반 이상이어야 하며, 연합 중 임의의 한 정당을 뺐을 때 연합의 인원수의 합이 전체 정당의 인원수의 반 미만이 되는 것을 모두 만족해야 합니다. 위 조건을 모두 만족하는 연합 중 가장 많은 인원수를 가지는 연합을 찾는 문제입니다. 문제를 그리디로 접근하면, 정당의 인원수가 많은 것부터 보면서, 전체 정당의 인원수의 절반($ \frac{(\sum_{i=1}^n A_{i})}{2} $)을 처음으로 ..
2020.10.12 -
백준 2098번, 외판원 순회 풀이
문제 백준 2098번 풀이 DP 점화식을 $ dp[i][j] = i\ 정점에\ 방문했을\ 때\ j\ 정점들에\ 방문한\ 경우의\ 최솟값 $ 이라고 두겠습니다. $ j $만큼 방문했다는 것은 어떤 정점들에 방문했는지에 대해서 기록해둔다는 의미입니다. 이 $ j $를 비트마스킹을 사용하여 처리할 것입니다. 일반적인 vector 등을 사용하여 처리할 수도 있지만, vector를 매번 재귀 함수의 매개변수로 넘겨주기에는 cost가 작지 않기 때문입니다. $ j $를 이진수 정수로 두고 숫자 읽듯이 오른쪽부터 왼쪽 순서대로 읽을 겁니다. 그러면, 0번째 자리는 0번 정점에 방문했는지, 1번째 자리는 1번 정점에 방문했는지.. $ k $번째 자리는 $ k $번 정점에 방문했는지에 대한 정보를 담을 수 있습니다. 예..
2020.10.08 -
백준 5550번 (JOI 2011년 2번), 헌책방 풀이
문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..
2020.09.27