DP5 [BOJ] 백준 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 행렬 곱셈 순서에 따라 연산량이 적어지는데 잘 생각해보면 (a b) (b c) 차원인 두 행렬을 곱할 때 a * b * c 의 연산횟수가 필요하다. 즉 가운데 b가 큰 순서대로 먼저 곱하는것이 횟수를 줄일 수 있다. 하지만 당장 b가 큰것을 줄이는 순서가 최종적으로 최적의 방법이 아닐 수 있기 때문에 구간 s~e 에서 모든 연산을 수행해봐야 한다. DP[s][e]를 s 번째 행렬과 .. 2020. 8. 6. [BOJ] 백준 2225번: 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0~N까지 정수 K개를 더하여 N을 만드는 경우의 수를 구하는 문제입니다. 이를 식으로 나타내면 아래와 같습니다. 각 a의 값은 0 이상이므로 중복 순열의 식으로 구할 수 있습니다. #include #include #include #include #include #include #include #include #define MOD (1000000000) using namespace std; int n, m; int ncr[401][401] = { 0, }; int main() { ios_base::sync_with_stdi.. 2020. 6. 29. [BOJ] 백준 1509번: 팰린드롬 분할 Class 5에는 대부분 DP로 구성된 것 같네요 recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면 i = e) { return pal[s][e] = 1; } int& ret = pal[s][e]; if (~ret) return ret; ret = 0; if (str[s] == str[e]) { return ret = ispal(s + 1, e - 1); } return ret; } int recv(int node) { if (node == n) { return 0; } int& ret = dp[node]; if (~ret) return ret; ret = 2e9; for (int i = node; i < n; i++) { if (ispal(node, i.. 2020. 6. 25. [BOJ]백준 1167번: 트리의 지름 1번 정점을 루트로 가정하고 dp[i]를 i번째 정점을 서브 트리의 루트로 가정했을때 가장 긴 지름을 저장함 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; int n; vector v[100001]; int dp[100001]; // i 를 루트로 했을때 지름 길이 int recv(int node, int p) { int& ret = dp[node]; if (~ret) return ret; ret = 0; int _max1 = 0, _max2 = 0; for (auto nxt : v[node]) { int _node = nxt.first; int .. 2020. 6. 19. 이전 1 2 다음
