반응형
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public class FastSum {
public static void main(String[] args) {
System.out.println(fastSum(10));
}
public static int fastSum(int n) {
if(n == 1) {
return 1;
}
if(n%2 == 1) return fastSum(n-1) + n;
return 2*fastSum(n/2)+n/2*n/2;
}
}
|
cs |
1 + 2 + 3 + 4 + 5 + ... + n 을 반으로 나누어서 계산해 보자
1 + 2 + 3 + ... n/2 + (n/2+2) + (n/2+3) + (n/2+4) + (n/2+n/2)
= f(n/2) + n/2*n/2 +f(n/2)
=> 2f(n/2) + n/2*n/2 가 된다.
n은 짝수일때 성립한다.
위의 코드를 보면 n이 홀수일 때는 f(n-1) + n을 하여 홀수일 때를 처리해 준다.
1부터 n 까지 더해주는 반복문은 무조건 n번 반복해서 수를 더해준다.
하지만 위의 코드를 보면 n이 짝수가 될때마다 n을 2로 나누어서 계산하기 때문에 훨씬더 빠르게 계산되는 것을 알 수 있다.
반응형
'알고리즘 > 알고리즘 문제해결전략' 카테고리의 다른 글
문제 ID : CLOCKSYNC, 난이도: 중 (0) | 2020.11.23 |
---|---|
예제 : 여행하는 외판원 (0) | 2020.11.09 |
문제 ID : BOARDCOVER , 난이도: 하 (0) | 2020.11.04 |
문제 ID : PICNIC, 난이도: 하 (0) | 2020.11.02 |