[1265번] 달란트2

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18R8FKIvoCFAZN

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

dp의 상태식을 정의한다.

dp[i][j] :: i개 남았고 그때 m번만에 했을 때 최댓 값

이를 통해 재귀식을 만들어내면 정답을 도출 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #include <algorithm>   using namespace std;   typedef long long ll;   ll dp[102][102]; int n;   ll solve(int remain, int m) {     if (remain == 0 && m == 0)         return 1;       ll &ret = dp[remain][m];       if (ret != -1)         return ret;       ret = 0;       for (int i = 1; i <= remain; i++)          if (m - 1 >= 0 && remain > 0)              ret = max(ret, solve(remain - i, m - 1) * i);          return ret; }   int main() {     freopen("input.txt", "r", stdin);     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {           for (int i = 0; i < 102; i++)             for (int j = 0; j < 102; j++)                 dp[i][j] = -1;         int m;         scanf("%d %d", &n, &m);           ll ret = solve(n, m);           printf("#%d %lld\n", tc,ret );     }     return 0; } Colored by Color Scripter

cs