백준 28017번 : 게임을 클리어하자

• Solved.ac 기준 : 골드 5
• 사용언어 C++

문제 해석 및 풀이

• DP 활용
• 이전 회차 무기 다음 회차 사용 불가능
• DP 배열 dp[i][j]를 사용하여 i번째 회차에서 j번 무기를 사용했을 때의 최소 총 시간을 저장합니다.
• dp[i][j]는 i-1번째 회차에서 k번 무기를 사용했을 때의 최소 시간에 i번째 회차에서 j번 무기를 사용했을 때 걸리는 시간을 더한 값 중 최솟값이 됩니다. (k != j)
  -dp[i][j] = min(dp[i-1][k]) + time[i][j] (k != j)
  처음 시작할 때, dp[0][j] = time[0][j] (첫 번째 회차에서 각 무기를 선택했을 때의 시간)

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	vector < vector<int>> time(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> time[i][j];
		}
	}

	vector<vector<int>> dp(n, vector<int>(m, INT_MAX));

	for (int j = 0; j < m; j++) {
		dp[0][j] = time[0][j];
	}

	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			for (int k = 0; k < m; ++k) {
				if (j != k) {
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + time[i][j]);
				}
			}
		}
	}

	int res = INT_MAX;

	for (int j = 0; j < m; j++) {
		res = min(res, dp[n - 1][j]);
	}

	cout << res;

	return 0;
}