[백준/BOJ] 17953 디저트

문제 : 17953 디저트

17953번: 디저트

각 날마다 디저트가 주는 만족감이 주어질 때, 최대로 얻을 수 있는

만족감을 출력하는 문제이다.

날짜를 N, 디저트의 종류를 M이라 할 때 그냥 모든 경우의 수를 구하면

O(M^N)이므로 당연히 시간 초과가 난다.

DP 배열을 만들어 전날까지의 만족감 중 최대를 골라 계속 갱신해주면 

O(N*M^2)로 시간제한 안에 해결할 수 있다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, arr[15][100005], DP[15][100005], ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=1;i<=M;i++){
        for (int j=1;j<=N;j++){
            cin >> arr[i][j];
        }
    }
    for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++){
            ll tmp=0;
            for (int k=1;k<=M;k++){
                if (i!=1 && j==k)
                    tmp=max(DP[k][i-1]+arr[j][i]/2,tmp);
                else
                    tmp=max(DP[k][i-1]+arr[j][i],tmp);
            }
            DP[j][i]=tmp;
        }
    }
    for (int i=1;i<=M;i++)
        ans=max(DP[i][N],ans);
    cout << ans;
    return 0;
}