분할정복으로 1부터 n까지 합 구하기

int func(int n) {
if (n == 1) return 1;
else if (n % 2 == 1) return n + func(n - 1);
else return func(n / 2) * 2 + (n*n) / 4;
}

 

1 + 2 + ... + n

-> (1 + 2 + ... n/2) + ((n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2))

-> (1 + 2 + n/2) * 2 + (n/2 * n/2) // n/2가 n/2개 있음으로 뒤로 뺀다

 

따라서 n이 짝수일 때 f(n) = f(n/2)*2 + (n*n)/4

n이 홀수일 땐 f(n) = n + f(n-1)

n이 1이면 1을 반환