[Ch.03 - 투 포인터] 5. 연속된 자연수의 합 # (+ for-while)

5. 연속된 자연수의 합

양의 정수 N을 2개 이상의 연속된 자연수 합으로 표현하는 가짓수 출력

 

입력값

15

출력값

3

 

---

package twopointer.ch03;

import java.util.Scanner;

//연속된 자연수의 합
//자연수 N을 2개 이상의 연속된 자연수 합으로 만드는 가지수 M출력
public class Twopointer05 {
	public int solution(int n) {
		int answer=0;
		int p1=1;
		int p2=2;
		int sum=0;
		while(p1<n) {
			sum=p1;
			p2=p1+1;
			while(sum<=n&&p2<n) {
				sum+=p2++;
				if(sum==n) {
					answer++;
				}
			}
			p1++;	
		}
		return answer;
	}
	public static void main(String[] args) {
		Twopointer05 T =new Twopointer05();
		Scanner kb =new Scanner(System.in);
		int n=kb.nextInt();
		System.out.println(T.solution(n));		
	}

}

-> 배열에 넣지 않고, 값만 가지고 투포인터를 이용해 구현

 

import java.util.Scanner;

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

}

-> 값을 배열에 넣고, 투포인터를 이용해 구현

 

 

+)세련된 풀이 1. 투포인터 사용

1. 자연수 n의 1/2 +1값을 m으로 설정

m까지 배열에 수열을 순서대로 넣는다.

2. for(int rt=0;rt<m;rt++)

포인터2는 m까지 반복하면서, 합계에 추가

3. if(sum==n)

만약 합계가 원하는 값이 된다면, 결과에 +1

4. while(sum>=n)

합계보다 원하는 값이 크면, 포인터1의 값을 합계에서 뺀다.

5. if(sum==n)

포인터1의 값을 합계에서 빼면서 합계가 원하는값이되면, 결과값+1

package twopointer.ch03;

import java.util.Scanner;

public class Twopointer05_1 {
	//연속된 자연수의 합 (Twopointer)
	//N이 양수이면, 2개 이상의 연속된 자연수 합으로 N표현하는 가짓수를 출력
	
	public static void main(String[] args) {
		Twopointer05_1 T = new Twopointer05_1();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		System.out.println(T.solution(n));
		kb.close();
	}
	
	public int solution(int n) {
		//1.ds
		int answer=0, sum=0;
		int m=n/2+1;
		int[] arr = new int[n];
		
		for(int i=0;i<m;i++) {
			arr[i]=i;
			//0,1,2,3,...순으로 추가
		}
		int lt=0;
		//포인터1
		
		//2.for
		for(int rt=0;rt<m;rt++) {
			//포인터2는 m까지 반복
			sum+=arr[rt];
			//m까지 합계에 추가
			
			if(sum==n)
				answer++;
			//만약 합계가 원하는 값이 된다면, 결과에 +1
			while(sum>=n) {
				sum-=arr[lt++];
				//합계보다 원하는 값이 크면, 포인터1의 값을 합계에서 뺀다.
				if(sum==n)
					answer++;
				//포인터1의 값을 합계에서 빼면서 합계가 원하는값이되면, 결과값+1
			}
		}
		return answer;
	}

}

 

 

 

 

 

+) 2. 수학 이용

 

 

n이 연속된 자연수 X개로 분리된다면, n에서 1, 2, ..x를 뺀 값이 2로 나누어 떨어진다. 1. 15가 자연수 2개로 분리 (1) 15가 2개로 분리된다면, n에서 1,2를 뺀 12가 2로 나누어 떨어진다. (2) 즉, 12/2의 몫 6에 각각 1과 2를 더하면, 7,8이 되고 이의 합이 15가 된다. 2. 15가 자연수 3개로 분리 (1) 15가 3개로 분리된다면, n에서 1,2,3을 뺀 9가 3으로 나누어 떨어진다. (2) 즉, 9/3의 몫 3에 각각 1,2,3을 더하면, 4,5,6이 되고 이의 합이 15가 된다. 3. 15가 자연수 4개로 분리 (1) 15가 4개로 분리된다면, n에서 1,2,3,4를 뺀 5가 4로 나누어 떨어지지 않는다. 4. 15가 자연수 5개로 분리 (1) 15가 5개로 분리된다면, n에서 1,2,3,4,5를 뺀 0이 5로 나누어 떨어진다, (2) 즉, 0/5의 몫 0에 각각 1,2,3,4,5를 더하면 1,2,3,4,5가 되고 이의 합이 15가 된다.

 

1. int answer=0, cnt=1;
결과는 0 카운트는 1로 초기화, 원하는 값에서 -1을 한다.

2.while(n>0)

원하는 값이 0보다 크면 카운트를 하나씩 늘리고, 원하는 값에서 카운트를 뺴는 것을 반복하는데,

3.if(n%cnt==0)

카운트를 나눴을때 나머지가 0인경우 결과에 +1한다.

 

즉, 5인경우 n은 4가 되고, 카운트는 2가 된다.
4/2==0이므로, 결과값을 하나 추가한다.

-> 5인경우 2,3으로 하나가 된다.

 

package twopointer.ch03;

import java.util.Scanner;

public class Twopointer05_2 {
	// 연속된 자연수의 합 (수학)
	// N이 양수이면, 2개 이상의 연속된 자연수 합으로 N표현하는 가짓수를 출력
	public int solution(int n) {
		//1.ds
		int answer=0, cnt=1;
		//결과는 0 카운트는 1로 초기화
		n--;
		//원하는 값을 하나 줄이면서
		
		//2.for,while
		while(n>0) {
			cnt++;
			n=n-cnt;
			if(n%cnt==0)
				answer++;
			//원하는 값이 0보다크면 카운트를 하나씩 늘리면서
			//카운트를 나눴을때 나머지가 0인경우 결과에 +1한다.
			//5인경우 n은 4가 되고, 카운트는 2가 된다.
			//4/2==0이므로, 결과값을 하나 추가한다.
			//5인경우 2,3으로 하나가 된다.
					
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Twopointer05_2 T = new Twopointer05_2();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.println(T.solution(n));
		kb.close();
	}
	
}

 

(1) 1부터 하나씩 n전까지 더하면서 n이 될 때만 체크

(2) 더한합이 n보다 크면, 작아질 때까지 앞에서부터 자르면서 n이 되는지 체크

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(solution(n));
  }
  static int solution(int n){
    int answer=0;
    int lt=1;
    int rt=n;
    int sum=0;
    for(int i=1;i<n;i++){
      sum+=i;
      if(sum==n) answer++;
      while(sum>n){
        sum-=lt;
        lt++;
        if(sum==n) answer++;
      }
    }
    return answer;
  }
}

---

1. for-while문 이용

 

(1) lt는 계속 돌면서 lt마다 rt를 돌리면서 원하는 N보다 크면 멈춤

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int rt=0;
    int answer=0;
    for(int lt=1;lt<=(n/2); lt++){
      int sum=lt;
      rt=lt+1;
      while(rt<n){
        sum+=rt++;
        if(sum==n) answer++;
        if(sum>n) break;
      }
    }
    System.out.println(answer);
  }
}

 

(2) sum이 더 크면 크지 않을때까지 lt를 하나씩 삭제

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int m=n/2+1;
    int sum=0;
    int lt=1;
    int answer=0;
    for(int rt=1; rt<=m; rt++){
      sum+=rt;
      if(sum==n) answer++;
      while(sum>=n){
        sum-=lt++;
        if(sum==n) answer++;
      }
        
    }
    System.out.println(answer);
  }
}

---

+) 03.02

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    Main main = new Main();
    System.out.println(main.solution(n));
  }
  public int solution(int n){
    int result=0;
    int answer=0;
    int p1=1;
    for(int i=1;i<=n/2+1;i++){
      result+=i;
      if(result==n) answer++;
      
      while(result>n){
        result-=p1++;
        if(result==n) answer++;
      }
    }
    return answer;
  }
}