DP (2) 썸네일형 리스트형 백준 합분해 2 13707 (c++) 문제 https://www.acmicpc.net/problem/13707 13707번: 합분해 2 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다. www.acmicpc.net 오랜만에 c++로 문제 풀려고 풀어봤다. dp로 풀었기 때문에 점화식만 구하면 쉽게 풀 수 있는 문제였다. 재귀로 풀어서 좀 오래 걸린 것도 있고, 다른 사람들 코드 보니까 더 간단하게 풀기도 했다. 점화식은 다음과 같다. arr [k][n]으로 놓고 k개를 사용해서 n을 만들 수 있는 경우의 수를 구하면 된다. arr [k][n] = arr [k-1][0]+ arr [k-1][1].... arr [k-1][n] 이런 식으로 되는데 더하는 경우가 각각 마지막에 n, n-1, n-2..... 백준 11049 행렬의 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP로 접근해서 해결한 문제입니다. 점화식이 쉽게 생각나지 않아서 도움을 많이 받았습니다. 이 문제는 주어진 행렬의 곱셈 순서에 따라 연산 횟수가 달라지는데 그중 최소 연산 횟수를 찾는 문제입니다. 과정은 다음과 같습니다. 값을 저장할 dp 리스트를 이차원으로 만듭니다 dp [i][j] = i행렬부터 j행렬까지의 최소 연산 행렬 간의 곱을 여러 경우로 만들어 낼 수 있어서 시작 .. 이전 1 다음