백준_2018_연속된 자연수의 합 구하기(투 포인터)

수들의 합 5 

 

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

2 초

32 MB

36319

17838

13029

49.140%

문제

어떠한 자연수 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

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO March 2003 Contest > Orange 2번

• 문제의 오타를 찾은 사람: yukariko
• 데이터를 추가한 사람: momiens

 

---

시작 인덱스와 종료 인덱스를 사용 

-> 시작 인덱스를 오른쪽으로 한 칸 이동 = 연속된 수에서 왼쪽 값을 하나 삭제하는 것

-> 종료 인덱스를 오른쪽으로 한 칸 이동 = 연속된 자연수의 범위를 한 칸 더 확장

 

 

count =1 로 초기화 시키는 이유는 

예제 입력이 15라면 15만 뽑는 경우의 수를 미리 넣고 초기화하기 위함.

 

 

*암기

if(sum=N) count증가, end_index 증가, sum = sum + end_Index;

else if(sum < N) end_index++, sum = sum + end_Index;

else if(sum > N) sum = sum - start_Index, start_Index++;

 

 

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        //변수 초기화
        int count =1;
        int sum =1;
        int start_index=1;
        int end_index = 1;
       
        while(end_index != N){
            if(sum < N){
                end_index++;
                sum = sum+end_index;
            }
            else if(sum > N){
                sum = sum-start_index;
                start_index++;
            }
            else if(sum == N){
                count++;
                end_index++;
                sum = sum + end_index;
            }
        }
        System.out.println(count);
           
    }
}