7285 : 분할정복 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
분할 정복(Divide and Conquer)을 이용하여 배열의 전체 합을 구하십시오.
배열을 이분 분할하여 재귀적으로 구간합을 구합니다.
반복문을 사용하지 않고 재귀로만 구현해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
배열을 이분 분할하여 재귀적으로 구간합을 구합니다.
반복문을 사용하지 않고 재귀로만 구현해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
배열을 분할 정복으로 계산한 전체 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 2 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
def dc_sum(arr, l, r): if l==r: return arr[l]; mid=(l+r)//2; return dc_sum(arr,l,mid) + dc_sum(arr,mid+1,r)