어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1<=N<=10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이때 사용하는 자연수는 N 이여야 한다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5 이다. 반면, 10을 나타내는 방법은 10, 1+2+3+4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.
입력
1번째 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.
예제 입력 1
15 // N
예제 출력 1
4
코드
import java.util.Scanner;
public class P2018_연속된자연수의합 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 1;
int start_index = 1;
int end_index = 1;
int sum = 1;
while(end_index != N) {
if(sum == N){
count++;
end_index++;
sum = sum + end_index;
} else if(sum > N){
sum = sum - start_index;
start_index++;
} else {
end_index++;
sum = sum + end_index;
}
}
System.out.println(count);
}
}
투 포인터 이동 원칙을 이용해서 접근하면 되는 문제이다.
1~15 을 1번째부터 start_index, end_index 로 시작하고, sum 이 15가 될 때까지 end_index 를 이동시키고, 15가 되는 경우 start_index를 이동한다.
start_index -->
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
end_index -->
투 포인터 이동 원칙
sum > N : sum = sum - start_index; start_index++;
sum < N : end_index++; sum = sum + end_index;
sum == N : end_index++; sum = sum + end_index; count++;
Reference
백준의 올라인 저지 2018번