반응형
다차원 동적 계획법 (Multidimensional DP)
다차원 동적 계획법은 상태를 여러 차원으로 정의하여 문제를 해결하는 기법입니다. 이 방법은 주로 상태를 더 구체적으로 나누어 관리할 때 사용됩니다. 예를 들어, 3차원 DP는 dp[i][j][k]와 같이 상태를 표현할 수 있습니다.
문제 예시: 3차원 DP를 이용한 여행 계획
주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 3차원 DP를 사용할 수 있습니다. 여기서 dp[i][j][k]는 i번째 도시를 j번째 날에 k번 방문했을 때의 최소 비용을 의미합니다.
다차원 DP 구현
다음은 C++로 3차원 DP를 사용하여 문제를 해결하는 예제입니다.
문제 정의
주어진 도시들의 방문 비용이 포함된 cost 행렬이 있습니다. 여행자는 특정 순서로 도시들을 방문하며, 동일한 도시는 최대 max_visits 번까지 방문할 수 있습니다. 목표는 여행자의 전체 여행 비용을 최소화하는 것입니다.
다차원 DP 예제
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
// 최대 방문 가능한 도시 수
const int MAX_CITIES = 100;
// 최대 방문 가능한 날 수
const int MAX_DAYS = 100;
// 최대 방문 가능한 횟수
const int MAX_VISITS = 10;
int main() {
int numCities, numDays, maxVisits;
std::cin >> numCities >> numDays >> maxVisits;
// 도시 방문 비용 행렬
std::vector<std::vector<int>> cost(numCities, std::vector<int>(numCities));
for (int i = 0; i < numCities; ++i) {
for (int j = 0; j < numCities; ++j) {
std::cin >> cost[i][j];
}
}
// 3차원 DP 테이블 초기화
std::vector<std::vector<std::vector<int>>> dp(MAX_CITIES, std::vector<std::vector<int>>(MAX_DAYS, std::vector<int>(MAX_VISITS, INT_MAX)));
// 시작점 설정
dp[0][0][1] = 0;
for (int day = 1; day <= numDays; ++day) {
for (int city = 0; city < numCities; ++city) {
for (int visit = 1; visit <= maxVisits; ++visit) {
if (dp[city][day - 1][visit - 1] != INT_MAX) {
for (int nextCity = 0; nextCity < numCities; ++nextCity) {
dp[nextCity][day][visit] = std::min(dp[nextCity][day][visit], dp[city][day - 1][visit - 1] + cost[city][nextCity]);
}
}
}
}
}
// 최소 비용 계산
int minCost = INT_MAX;
for (int city = 0; city < numCities; ++city) {
for (int visit = 1; visit <= maxVisits; ++visit) {
minCost = std::min(minCost, dp[city][numDays][visit]);
}
}
std::cout << "최소 여행 비용: " << minCost << std::endl;
return 0;
}
설명
- 입력:
numCities: 도시의 수numDays: 여행 일수maxVisits: 각 도시의 최대 방문 횟수cost: 도시 간 이동 비용 행렬
- 3차원 DP 테이블:
dp[i][j][k]는 i번째 도시를 j번째 날에 k번 방문했을 때의 최소 비용을 의미합니다.- 초기값으로
INT_MAX를 설정하여 불가능한 상태를 표시합니다.
- 동적 계획법 점화식:
dp[nextCity][day][visit] = std::min(dp[nextCity][day][visit], dp[city][day - 1][visit - 1] + cost[city][nextCity])- 이전 날 방문한 도시에서 다음 도시로 이동하는 비용을 계산합니다.
- 결과 출력:
- 모든 도시에서 가능한 최소 비용을 계산하여 출력합니다.
다차원 동적 계획법의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 16: DP 최적화 기법(Convex Hull Trick, Divide and Conquer Optimization)"에 대해 학습하겠습니다.
반응형