[JAVA][백준][S5] 2018번 수들의 합 5

https://www.acmicpc.net/problem/2018

 

📒 문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

● 시간 제한 / 메모리 제한

 2초 / 32MB

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

입출력 예

# 입력1
15

# 출력1
4

 

알고리즘 분류

• 수학
• 투 포인터

---

💻 소스코드

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 자연수 N

		int sum = 1;
		int result = 1;

		int start = 1;
		int end = 1;

		while(end != N){
		  if(sum > N){
				sum -= start;
				start++;
		  }
		  else if(sum < N){
				end++;
				sum += end;
		  }
		  else if(sum == N){
				result++;
				end++;
				sum += end;
		  }
		}

		bw.write(String.valueOf(result));
	
		bw.flush();
		bw.close();
    }   
}

📝 풀이

투 포인터를 사용해서 문제를 해결했다.

 

start 포인터(연속된 수의 시작점)와 end 포인터(연속된 수의 끝점)를 만들고

연속된 수의 합이 자연수 N보다 크면 시작 포인터를 옮기고,
연속된 수의 합이 자연수 N보다 작으면 end 포인터를 옮겼다.
연속된 수의 합이 자연수 N과 같으면 result에 +1을 해주고 end 포인터를 옮겨준다.