Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 동적 계획법으로 푸는 최대 휴가 일수 문제

한 회사가 우수 직원 한 명에게 N개의 도시를 돌며 자원을 수집할 수 있는 기회를 주려고 합니다. 하지만 직원 역시 휴가가 필요하죠. 특정 도시와 특정 주(week)에만 휴가를 사용할 수 있을 때, 여행 일정을 잘 짜서 최대한 많은 휴가 일수를 확보하는 것이 우리의 과제입니다. 단, 몇 가지 규칙과 제약 조건을 반드시 따라야 합니다.

문제 조건

  • 이동은 N개의 도시 사이에서만 가능하며, 각 도시는 0부터 N-1까지의 인덱스로 표현됩니다. 첫째 날(월요일)에는 인덱스 0번 도시에서 출발합니다.

  • 도시들은 항공편으로 연결되어 있습니다. N x N 크기의 flights 행렬이 항공편 정보를 나타내며, flights[i][j]가 0이면 i번 도시에서 j번 도시로 가는 항공편이 없다는 뜻이고, 그렇지 않으면 1입니다. 이 행렬은 대칭이 아닐 수도 있으며, 모든 i에 대해 flights[i][i] = 0입니다.

  • K주 동안 여행합니다. 하루에 비행기는 최대 한 번만 탈 수 있고, 매주 월요일 아침에만 비행기를 탈 수 있습니다.

  • 도시별·주별로 사용할 수 있는 휴가 일수는 제한되어 있으며, N x K 크기의 days 행렬이 이 관계를 나타냅니다. days[i][j]는 j번째 주에 i번 도시에서 보낼 수 있는 최대 휴가 일수를 의미합니다.

flights 행렬과 days 행렬이 주어졌을 때, K주 동안 쉴 수 있는 최대 휴가 일수를 구하는 것이 목표입니다.

예를 들어 flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]이라면 정답은 12가 됩니다.

해결 전략: 동적 계획법(DP)

이 문제는 뒤쪽 주부터 거꾸로 계산하는 방식의 동적 계획법으로 깔끔하게 해결할 수 있습니다. 핵심은 dp[i][j]를 "j번 도시에 머무는 상태에서 i번째 주부터 마지막 주까지 얻을 수 있는 최대 휴가 일수"로 정의하는 것입니다.

다음 순서로 진행합니다.

  • n := flights 행렬의 행 개수

  • m := days 행렬의 열 개수

  • (m + 1) x n 크기의 2차원 배열 dp를 정의합니다.

  • i를 m-1부터 0까지 감소시키며 반복합니다.

    • j를 0부터 n-1까지 증가시키며 반복합니다.

      • k를 0부터 n-1까지 증가시키며 반복합니다.

        • j == k(현재 도시에 계속 머무는 경우)이거나 flights[j][k]가 0이 아니면(j에서 k로 가는 항공편이 있는 경우):

          • dp[i][j] := max(dp[i][j], days[j][i] + dp[i+1][k])로 갱신합니다.

모든 dp 값을 채운 후에는 출발 도시가 0번으로 고정되어 있으므로 최종 답을 구합니다.

  • ret := dp[0][0]

  • i를 1부터 n-1까지 증가시키며, flights[0][i]가 0이 아니면 ret := max(ret, dp[0][i])로 갱신합니다.

  • ret을 반환합니다.

시간 복잡도는 O(K × N²), 공간 복잡도는 O(K × N)으로, 완전 탐색에 비해 훨씬 효율적으로 문제를 해결할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size();
        int m = days[0].size();
        vector<vector<int> > dp(m + 1, vector<int>(n));
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (j == k || flights[j][k]) {
                        dp[i][j] = max(dp[i][j], days[j][i] + dp[i + 1][k]);
                    }
                }
            }
        }
        int ret = 0;
        ret = dp[0][0];
        for (int i = 1; i < n; i++) {
            if (flights[0][i]) {
                ret = max(ret, dp[0][i]);
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}};
    cout << (ob.maxVacationDays(v1, v2));
}

입력

v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}

출력

12