[백준][C++] 17953: 디저트

문제 링크: https://www.acmicpc.net/problem/17953

 

dp 문제입니다.

dp[i][j] = j번째 날에 i번째 디저트를 먹었을 때의 최대 만족감

이렇게 놓고 푸시면 되겠습니다.

배열 인덱스가 좀 헷갈리는 문제네요..

#include <bits/stdc++.h>
using namespace std;


int happiness[10][100000];
int dp[10][100000];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
			cin >> happiness[i][j];

	for (int i = 0; i < m; ++i)
		dp[i][0] = happiness[i][0];

	for (int j = 1; j < n; ++j) {
		for (int i = 0; i < m; ++i) {	// j번째 날에 먹을 거
			auto mx = 0;

			for (int k = 0; k < m; ++k) {	// 전날 먹은거
				if (i == k)
					mx = max(mx, dp[k][j-1] + happiness[i][j] / 2);
				else
					mx = max(mx, dp[k][j-1] + happiness[i][j]);
			}

			dp[i][j] = mx;
		}
	}

	auto mx = 0;
	for (int i = 0; i < m; ++i)
		mx = max(mx, dp[i][n - 1]);
	cout << mx << '\n';

	return 0;
}