백준/DP (67) 썸네일형 리스트형 백준 1750 - 서로소의 개수 icpc.me/1750 수열이 주워지고 이들의 조합으로 만든 집합 중 원소들이 서로소가 됨을 만족하는 것 개수를 구하는 문제이다. DP 테이블 구성이 어려울 수 있으나 집합의 개수와 유사한 형태로 짤 수 있다. 집합의 개수를 먼저 풀고 오는 게 이 문제를 보는데 도움이 될 수 있다. 테이블의 정의는 다음과 같이 된다. DP[i][j] := i번째까지 원소 중에서 최대공약수가 j가 되게 하는 원소들로 이루어진 공집합이 아닌 집합의 개수 DP 테이블을 구성하더라도 어떻게 채우는지는 아직 감이 오지 않을 수 있다. 하지만 집합의 개수를 생각하여 다음과 같은 점화식을 생각할 수 있을 것이다. k := gcd(j, k) = j라고 한다면 DP[i][j] += DP[i - 1][j] + DP[i - 1][k] i .. 백준 2228 - 구간 나누기 icpc.me/2228 M개 구간을 인접하지 않게 모두 사용하여 구간들의 합을 최대화시키는 문제이다. 동적계획법으로 풀 수 있으며 3차원, 2차원으로 메모이제이션을 할 수 있다. 풀이 - 3차원 DP 더보기 3차원으로 풀기 위해 다음과 같이 테이블을 설계한다. dp[i][j][k] := i번째 구간에서 j번째 숫자를 택하고 길이 k만큼 부분합을 구했을 때 최대값 다중 for 문을 통해 다음 구간은 몇번째 숫자를 택할지, 길이는 얼마나 정할지에 대해 탐색하면서 최대값을 구하면 된다. 또한 각 수의 값은 -32768 이상 32767 이하이므로 dp 테이블을 초기화할 때 부분합으로 나올 수 있는 -32768 * 100 이상이나 32767 * 100 이하의 값은 피하면서 초기화를 해주어야 동적계획법 수행에 문제.. [KOI] 백준 2666 - 벽장문의 이동 icpc.me/2666 문제 이해와 그 접근 어떤 벽장을 사용하려는데 열려있다면 추가 비용 없이 그대로 이용할 수 있다. 만약 닫혀있다면 사용을 위해 벽장문을 밀어야 하는데 초기에 열린 벽장이 두개 주어지므로 닫혀있는 벽장을 열 수 없는 경우는 없다. 증명은 생략. 그렇다면 벽장문을 미는 경우는 두개로 나뉘어진다. 왼쪽으로 밀던가 오른쪽으로 밀던가. 동적계획법을 통해 이 두가지의 경우를 적절히 탐색하여 최소 비용을 찾아내면 될 것이다. 구현 dp 테이블을 이차원으로 구성했다. dp[i][j] := i번째 벽장을 열려고 하고 벽장이 j와 같은 상태일 때(비트마스크) 최소 비용 탑다운 dp를 통해 왼쪽으로 미는 비용과 오른쪽으로 미는 비용을 비교해서 최솟값을 구하면 된다. 각 방향마다 벽장문을 몇개 밀어야 .. 백준 2410 - 2의 멱수의 합 icpc.me/2410 이 문제는 DP 중에 유명한 유형인 동전 교환문제이다. $2^x$의 가치를 가진 동전이 무한히 있는 것으로 생각할 수 있다. dp 테이블은 다음과 같이 정의된다. dp[n] = 원소들을 모두 합해서 n이 되는 집합의 갯수 점화식은 다음과 같이 계산한다. $dp[n] += dp[n - 2^x]$ $n - 2^x$에서 $2^x$를 더하면 n이 되므로 이전에 계산된 $dp[n - 2^x]$를 모두 더하는 방식으로 dp[n]을 구할 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #define mod 1000000000 using namespace std; i.. 백준 1965 - 상자 넣기 icpc.me/1965 생각을 하다보면 LIS의 형태를 띄고 있음을 눈치챌 수 있다. $n \leq 1000$ 이므로 이진탐색을 쓰던 DP를 쓰던 LIS의 길이를 구해주자. 이전 1 ··· 8 9 10 11 12 13 14 다음
