[Java] 백준_수들의합5_2018

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

2018번: 수들의 합 5

 

문제 

어떠한 자연수 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

분석 

어떤 자연수 N을 입력받으면 연속된 자연수의 합으로 N을 표현할 수 있는 가지 수를 구하는 문제다. 주의할 점은 단순 for문으로 풀기에는 데이터 크기가 천만이라는 점이다. 시간 복잡도가 O(NlogN)이라고 해도 데이터 크기가 10,000,000이라면 10,000,000*log(10,000,000) = 10,000,000*23 = 230,000,000 즉 연산횟수가 2억이 넘어간다. 그렇기 때문에 주어진 시간 2초안에 문제를 해결할 수 없다. 이 문제에서 시간 복잡도를 O(N)로 맞춰야한다.  연속된 자연수의 합을 구해야하고 시간 복잡도가 O(N)이라는 점을 생각할 때 투포인터 알고리즘을 선택할 수 있다.

 

투포인터 이동 원칙

• sum > N  : 합이 N보다 크다면
  • sum -= arr[start]
  • start++
• sum < N : 합이 N보다 작다면 
  • end++
  • sum += arr[end]
• sum == N : 합이 N과 같다면
  • count++
  • end++
  • sum += arr[end]

시간복잡도

투포인터 알고리즘의 시간 복잡도는 O(N)이다. 데이터 갯수가 N개 일 때 최악의 경우 start, end 인덱스가 모두 끝까지 돌아야하기 때문에 O(2N)이고 상수를 제거하여 O(N)이 된다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 연속된자연수의합구하기_006 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int start = 1, end = 1;
        int sum = 1;
        int answer = 0;

        while (start <= end) {
            if (sum < n) {
                end++;
                sum += end;
            }
            else if (sum > n) {
                sum -= start;
                start++;
            }
            else if (sum == n){
                answer++;
                end++;
                sum += end;
            }
        }

        System.out.println(answer);
    }
}

결과