[알고리즘]Two pointers & Sliding window - 연속된 자연수의 합

5. 연속된 자연수의 합
양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램

입력) 첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.
출력) 첫 줄에 총 경우의 수를 출력합니다.

 

참고) n/2+1가 넘는 수를 더할 필요 없음. 예를 들어 N이 15라면 15/2+1은 8.

7+8이 15인데 8+9는 17.

즉, 8이 넘는 수를 더하면 무조건 N이 넘음.

 

 

1) 배열 사용

import java.util.Scanner;

public class Main {
	
	public static int solution(int n) {
		int answer = 0, sum = 0, lt = 0, m = n/2+1;
		int[] arr = new int[m];
		
		for (int i=0; i<m; i++) {
			arr[i] = i+1; // 1~m까지의 자연수
		}
		
		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) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		System.out.println(solution(n));
	}

}

 

2) 배열 사용X

import java.util.Scanner;

public class Main {
	
	public static int solution(int n) {
		int answer = 0, p1 = 1, sum = 0;
		
		for (int p2=1; p2<=n/2+1; p2++) {
			sum += p2;
			if (sum==n) answer++;
			while (sum>=n) {
				sum -= p1;
				p1++;
				if (sum==n) answer++;
			}		
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		System.out.println(solution(n));
	}

}

 

*수학적 방법

import java.util.Scanner;

public class Main {
	
	public static int solution(int n) { 
		int answer = 0, cnt = 1;
		n--;		
		
		while(n>0) {
			cnt++; // 연속된 자연수의 개수
			n = n-cnt;
			if (n%cnt==0) answer++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		System.out.println(solution(n));
	}

}

---

결과