[백준] 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

문제풀이

package doit_java;

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

public class doit_6_투포인터 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N, sum , result , startIndex, endIndex, 선언
        int N = Integer.parseInt(st.nextToken());
        int result =1; // N값은 빼고 카운트하기 때문에 +1 부터 시작
        int startIndex =1;
        int endIndex = 1;
        int sum =1; // 1부터 시작

        //while문
        while(endIndex!=N){
            //sum이 N보다 작을 경우 -> 범위를 크게 해야함 -> endIndex +1추가
            if(sum<N){
                endIndex++;
                sum = sum+endIndex;
            }
            //sum이 n보다 큰 경우 ->현재 startIndex값을 sum에서 빼주고 startIndex +1 추가
            else if(sum>N){
                sum = sum-startIndex;
                startIndex++;
            }
            //같은 경우-> result+1 추가 해주고 endIndex+1추가 하고 sum에 endIndex 더해주기
            else{
                result++;
                endIndex++;
                sum = sum+endIndex;

            }
        }

        System.out.println(result);

        System.out.println("end~!~!");
    }
}

 

투 포인터 알고리즘을  사용하면 간단하게 해결할 수 있다. 

 

[알고리즘] Two Pointers 알고리즘이란?