이번 문제를 통해 분할 정복의 기본에 대해 배우고 실습해보도록 하겠습니다.

부분 문제의 답을 재귀 호출로 구하고 각 부분 문제의 답을 통해 전체 문제의 답을 구하는 분할 정복 알고리즘은 대게 3가지 구성 요소를 가지고 있습니다.

1. 문제를 더 작은 문제로 분할( Devide )

2. 각 문제의 답을 원래 문제에 대한 답으로 병합( Merge )

3. 더 이상의 분할이 필요하지 않은 작은 문제( Base case )

1 부터 n 까지의 합을 구하는 문제를 분할 정복 알고리즘으로 해결하는 프로그램을 작성하십시오.

* Sum(n)을 잘라 2개의 부분 문제인 Sum(n/2)로 만들고 이를 처리하는 형태로 문제를 해결할 것을 권장합니다.

이 방법으로 문제를 해결한다면 재귀 방법에 비해 호출 회수가 훨씬 적다는 장점이 있습니다. ( O(log n)만큼 소요 )

입력

양의 정수

출력

1부터 입력값까지 모든 정수의 합