투포인터/수들의 합 5 - 백준 2018번

수들의 합 5

시간 제한	메모리 제한
2초	32MB

 

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

예제 입력 1

15

예제 출력 1

4

 

---

public class Main {
	private int N;
	private int ans = 0;

	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.start();
	}

	private void start() throws Exception {
		//System.setIn(new FileInputStream("src/test/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		twoPointer();
		bw.write(ans + "\n");
		bw.close();
		br.close();
		return;
	}

	
	private void basic() {
		for (int first = 1; first <= N; first++) {
			int s = 0;
			for (int until = first; until <= N; until++) {
				if(first == until) s = until;
				else s += until;
				
				if(s == N) ans++;
				else if(s > N) break;
			}
		}
	}
	
	private void twoPointer() {
		int start = 1;
		int end = 1;
		int sum = 1;
		while(start<=end) {
			if(sum == N) ans++;
			if(sum < N) {
				end++;
				sum += end;
			} else if(sum >= N) {
				sum -= start;
				start++;
			}
		}
	}

	private void arithmeticSequence() {
		for (int first = 1; first <= N; first++) {
			int s = 0;
			for (int end = first; end <= N; end++) {
				if (first == end)
					s = end;
				else
					s = (end - first + 1) * (first + end) / 2; // 등차수열의 합

				if (s == N)
					ans++;
				else if (s > N)
					break;
			}
		}
	}
}

 

알고리즘	메모리	시간
기본 반복문	15812 kb	216ms
등차수열	14660 kb	268ms
투포인터 알고리즘	14632 kb	164ms

 

 

---

출처

백준 2018번

 https://www.acmicpc.net/problem/2018