자바 알고리즘 문제 풀이 Two pointers, Sliding window Q05_ 연속된 자연수의 합

설명

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

만약 N=15이면

7+8=15

4+5+6=15

1+2+3+4+5=15

와 같이 총 3가지의 경우가 존재한다.

입력

첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.

출력

첫 줄에 총 경우수를 출력합니다.

 

예시 입력1	예시 출력
15	3

 

코드

내가 입력한 코드

package twoPointers_SlidingWindow;

import java.util.Scanner;

public class Q05 {
	public int solution(int n) {
		int answer = 0, sum = 0,lt = 1;
		
		for(int rt = 1;rt < n;rt++) {
			
			sum += rt;
			if(n == sum) answer++;
			
			while(sum >= n) {
				
				sum -= lt++;
				
				if(n == sum) {
					answer++;
					break;
				}
				
			}// end of while
		}
		
		
		return answer;
	}
	
	public static void main(String[] args) {
		Q05 T = new Q05();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		
		System.out.println(T.solution(n));
	}
}

---

해설 코드

import java.util.*;
class Main {	
	public int solution(int n){
		int answer=0, sum=0;
		int m=n/2+1;
		int[] arr=new int[m];

		for(int i=0; i<m; i++) arr[i]=i+1;
		int lt=0;
		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));
	}
}

 

풀이 및 정리 

-