171012_11052_붕어빵 판매하기

#include <iostream> using namespace std; int main() {     int N;     cin >> N;          int dp[1001]={0};          for(int i=1; i<=N; i++)     {         cin >> dp[i];         if (i==1) dp[i]=dp[i];         for(int x=i; x>=i/2; x--)         {if(dp[i]<(dp[x]+dp[i-x])) dp[i]=dp[x]+dp[i-x];}     }     cout << dp[N]; }

1. dp[i]에 세트의 값을 입력받기

2. dp[i]를 만들 수 있는 세트로 쪼개서 가장 큰 dp[i] 찾기

 -> dp[i]=dp[i]+dp[0] //dp[0]=0으로 초기화 되어있기 때문에 자기 자신 값 그대로

dp[i]=dp[i-1]+dp[1] //dp[i-1]이 될 수 있는 최대값+dp[1] 

dp[i]=dp[i-2]+dp[2] //dp[i-2]가 될 수 있는 최대값+dp[2]의 최대값

.

.

.

dp[i]=dp[0]+dp[i]// 

 이 값들의 최대값을 for문으로 비교하면서 최대값을 dp[i]에 저장

3. i가 홀수 일 경우 dp[x/2+0.5]+dp[x/2] 값 이 후부터 자리가 바뀐 채로 덧셈 반복 ->(5,0)(4,1)(3,2)(2,3)(1,4)(0,5)

-> int는 나누기를 한 결과가 소수일 경우 나머지를 버림!

-> for(int x=i; x>=i/2; x--) for문 반복 조건