[백준2018] 수들의 합5 (Java)

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

수들의 합 5  

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

32 MB

29015

13992

10325

48.726%

문제

 

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1 복사

15

예제 출력 1 복사

4

 

---

풀이

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

public class 수들의합5 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int count = 1; // N 자기자신 미리 count
        int start = 1;
        int end = 1;
        int sum = 1;

        while(end != N){
            if(sum < N){
                end++;
                sum += end;
            } else if (sum > N) {
                sum -= start;
                start++;
            } else{
                count++;
                end++;
                sum += end;
            }
        }
        System.out.println(count);
    }
}

 

투포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다.

start와 end를 지정하여 연속된 수를 가지고 연속된 자연수의 합을 구해갑니다.

 

미리 자기자신 N 하나인 경우를 count 시켜놓고

 

end값이 N보다 작은동안

sum이 N보다 작다면 end를 증가시킨 후, sum에 더합니다.

sum이 N과 일치한다면 count 증가 후, end증가, sum에 end를 더합니다.

sum이 N보다 크다면 sum에서 start값을 뺀 후에 start값을 증가시킵니다.