동적 계획법 응용 : 정수 삼각형
∙문제 해결 방법 - 정수 삼각형을 직각 삼각형 형태로 표현할 경우, 임의의 좌표 (x, y)에 이동하기 위해서는 (x - 1, y -1) 또는 (x, y - 1)좌표를 거쳐야한다. - 임의의 좌표 (x, y)에서의 삼각형 정수 값을 tri(x, y)라고 하고, 꼭대기 좌표에서 (x, y)까지 이동할 때의 정수 합의 최댓값을 dp(x, y)라고 할 경우 아래의 식이 성립된다. - 꼭대기 좌표부터 시작하여 왼쪽에서 오른쪽으로 위에서 아래 방향으로 dp(x, y) 값을 계산하고, 최종적으로 삼각형 바닥에서 dp(x, y)의 최댓값 구한다. ∙ 정수 삼각형 문제의 솔루션 함수의 예 int solution(vector triangle) { vector dp = triangle; int n = triangle.s..
동적 계획법 응용 : 최소 비용 경로
∙ 최소 비용 경로 (minimum cost path) - 2차원 행렬의 각 셀에 정수 값 비용이 적혀 있을 때, 행렬의 좌상단에서 우하단까지 이동하기 위한 최소 비용을 계산하는 문제. 최소 경로 합 - 이동은 오른쪽 또는 아래쪽 방향으로만 가능 ∙ 문제 해결 방법 - 오른쪽 또는 아래쪽 방향으로만 이동할 수 있으므로, 임의이 좌표(x, y)에 도달하기 위해서는 (x-1,y) 또는 (x, y-1)좌표를 거쳐야 한다. - 임의의 좌표 (x, y)에서의 행렬 값(비용)을 m(x, y)라고 하고, 좌상단에서 (x, y)까지 이동하는 경로의 최소 비용을 C(x, y)라고 할 경우 아래의 식이 성립된다. C(x, y) =. min(C(x - 1, y), C(x, y - 1)) + m(x, y) - 좌상단 좌표부터..
