[PS] 인프런 강의 - Two Pointers, Sliding window, Math 5. 연속된 자연수의 합

 

문제

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

 

▣ 출력예제 1
3

 

풀이

연속 부분수열과 비슷하게 풀면된다.

풀이 2) N=15일 때 연속된 자연수의 합은 8까지만 체크하면 된다. 8+9=16이니까.

따라서 체크할 숫자 끝 값 = N/2 + 1 로 두고 푼다.

 

그런데 이것을 또 수학적으로 다르게 푸는 방식이 있다.

풀이 3) 15개를 연속된 자연수 cnt개로 분배할 경우를 구한다.

 

예를 들어 15를 2개로 분배할 경우

1. ○ + ○  여기에 1과 2를 할당한다.

2 그리고 15-1-2를 한 나머지를 2로 나눈다. 여기서 나누어 떨어지지 않으면 답이 아니다.

3. 그 값(6)을  ○ + ○ 여기에 분배하면 1+6, 2+6 으로 ○ + ○ = 7 + 8 = 15가 되므로 답이다. 즉 2번과정에서 나누어 떨어진다면 답으로 카운트하면된다.

 

cnt=2  n=12 (n-1=14 → n-=cnt. 14-2)  1(+6) + 2(+6) = 15

cnt=3 n=9 (n-=cnt. 12-3) 1(+3) + 2(+3) + 3(+3) = 15

cnt=4 n=5 (n-=cnt. 9-4) 15/4 != 0  답이 아님

cnt=5 n=0 (n-=cnt. 5-5) 1(+0) + 2(+0) + 3(+0) + 4(+0) + 5(+0) = 15

 

코드

1) 이중 for문이라서 n이 엄청 커진다면 시간 부족 에러가 뜰 것이다

1부터 합이 n이 될때까지 계속 더함
2부터 ..
3..
n-1 까지 반복

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int answer = 0;
		//2개 이상 연속된 자연수합으로 n을 표현하는 가짓수
		for(int i=1; i<n; i++) {
			int sum=i;
			for(int j=i+1; j<n; j++){
				sum+= j;
				if(sum==n) answer++;
			}
		}

		System.out.print(answer);
	}
}

 

2) 강사님 풀이

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; //1부터 체크할 숫자 개수
		int answer=0, sum=0;
	
		int[] arr = new int[n];
		for(int i=0; i<m; i++) {
			arr[i] = i+1; //0번 인덱스에 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++;
			}
		}

		System.out.print(answer);
	}
}

 

3) 수학적 풀이

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int answer=0, cnt=1; //cnt는 연속된 자연수의 개수
		n--; //1빼준다.
		while(n>0) {
			cnt++;//2
			n-= cnt; //n-1-2-3.. 유기적으로 연결됨
			if(n%cnt == 0) answer++;
		}

		System.out.print(answer);
	}
}