[백준/2018][Java] 수들의 합 5

2018번: 수들의 합 5

• 두개의 포인터를 활용하여 시작 인덱스와 끝 인덱스를 지정하여 합이 N이 되는 경우의 수를 구합니다.
• 합 < N : e이동(e+1), 누적
• 합 > N : s이동(s+1), 감소
• 합 == N : count+1 , s+1
• pseudo-code

/*pseudo-code*/
N // 목표 합
start = 1, end = 1 //시작, 끝 자연수 (포인터)
count = 0, sum = 1 //개수, start 부터 end까지 연속된 자연수의 합
while end<=N
		if sum == N then count++, start++, end++, sum 변경
		else if sum < N then end++, sum 변경
		else if sum > N then start++, sum 변경

시간 복잡도 O(n)

package algo0309;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B2018_수들의합5 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int start = 1, end = 1;
		int cnt = 0, sum = 1;
		while (end <= n) {
			{
				if (sum == n) {
					cnt++;
					end++;
					sum += end;
				} else if (sum < n) {
					end++;
					sum += end;
				} else if (sum > n) {
					sum -= start++;
				}
			}
		}
		System.out.println(cnt);

	}
}