블로그 언저리인 무언가

문제 : 17953 디저트 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나� www.acmicpc.net 각 날마다 디저트가 주는 만족감이 주어질 때, 최대로 얻을 수 있는 만족감을 출력하는 문제이다. 날짜를 N, 디저트의 종류를 M이라 할 때 그냥 모든 경우의 수를 구하면 O(M^N)이므로 당연히 시간 초과가 난다. DP 배열을 만들어 전날까지의 만족감 중 최대를 골라 계속 갱신해주면 O(N*M^2)로 시간제한 안에 해결할 수 있다. Code #include #define ll long long using namespace std; ll N, M..