5. 연속된 자연수의 합

import java.util.*;

class Main {
	public int solution(int N) {
		int answer = 0;
		for (int i = 1; i < N; i++) {
			int temp = 0;
			for (int j = i; j < N; j++) {
				temp += j;
				if (temp > N)
					break;
				else if (temp == N) {
					answer++;
					break;
				}
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		System.out.print(T.solution(N));
		kb.close();
	}

}

O(n^2)

 

import java.util.*;

class Main {
	public int solution(int N) {
		int answer = 0, sum = 0, lt = 0;
		int M = N / 2 + 1;
		int[] arr = new int[M];
		for (int i = 0; i < M; i++)
			arr[i] = i + 1;
		for (int rt = 0; rt < M; rt++) {
			sum += arr[rt];
			if (sum == N)
				answer++;
			while (sum >= N) {
				sum -= arr[lt++];
				if (sum == N)
					answer++;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		System.out.print(T.solution(N));
		kb.close();
	}
}

투 포인터 알고리즘으로 O(n)