[14606번] 피자 (Small)

문제 출처 :

https://www.acmicpc.net/problem/14606

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

dp 점화식을 세워 문제를 해결한다.

dp[i] :: i번째 최대 행복

dp[i] = (i / 2) * (i / 2) + dp[i / 2] + dp[i / 2]라는 방식을 통해 해결 할 수 있다.

반씩 나누었을 때 곱 + 이전 dp값을 이용하여 현재 dp를 갱신해주면 된다.

이 방법을 이용하면 Small은 충분히 통과할 수 있다.

소스 코드 : 

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

#include <iostream> #include <cstdio>   using namespace std;   int dp[12];   int main() {     int n;       scanf("%d", &n);     dp[1] = 0;     dp[2] = 1;          for (int i = 3; i <= 10; i++)     {         if (i % 2 == 1)             dp[i] = (i / 2) * (i / 2 + 1) + dp[i / 2] + dp[i / 2 + 1];         else             dp[i] = (i / 2)*(i / 2) + dp[i / 2] + dp[i / 2];     }       printf("%d", dp[n]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus