1부터 N까지의 합 구하기

For문

보통 1부터 N까지의 합을 구할 때 for문을 통해 누적 합산 시킨다.
이 경우 데이터의 수 만큼 반복문이 진행되기 때문에 O(n)시간 복잡도를 가진다.

import java.util.Scanner;

public class Example1 {
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int sum = 0;
		
		for(int i=1; i<=n; i++) {
			sum += i;
		}
		System.out.println(sum);
	}
}

가우스의 덧셈

1부터 n 까지의 합을 구할 때 1~n과 n~1을 더해주면 모든 수는 n+1이 된다.
n+1된 값이 n만큼 나오기 때문에 (n+1) * n 을 한 후
1~n과 n~1의 합이기 때문에 /2를 해주면 1~n만큼의 합만 구할 수 있다.
(n+1)*n / 2

이 경우 값의 증가와 상관없이 한 번의 계산만 하면 되기 때문에 O(1) 시간복잡도를 가진다.

import java.util.Scanner;

public class Example1 {
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int sum1 = (n+1)*n/2;
		int sum2 = (n+1)*(n/2)+(n%2==1?(n+1)/2:0);
		
		System.out.println("sum1 : " + sum1);
		System.out.println("sum2 : " + sum2);
	}
}