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

 

 

 

처음에 아래와 같이 했는데 시간초과가 떴다. 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        int [] arr = new int[n+1];
        int count =0;
        //n을 입력으로 받는다.
        // n은 1부터 시작한다.
        //연속된 자연수의 합으로 나타내는 가짓수
        //전체 배열의 구간합을 만들어 주어야 한다. 1. 첫번째 인덱스 부터 끝까지  2. 두번째 인덱스부터 끝까지 계속 구해준다.
        // 첫번재 인덱스부터 끝까지 구할때, 구간 합 중 n이 되는 것이 있다면 count해준다.

        for(int i=1;i<=n;i++){ //start
            for(int j=i;j<=n;j++){
                arr[j]=arr[j-1]+i;
                if(arr[j]==n){
                    count+=1;
                }
            }

        }

        System.out.println(count);

    }
}

 

 

 

 

성공한 코드  

n의 최댓값이 10,000,000으로 크게 잡혀있어, 시간 복잡도가 O(nlogn)이상을 사용하면 제한시간을 초과한다. 

그래서 아래와 같이 시간복잡도가 n인 코드로 바꿨다. 여기서 투 포인터를 사용하였는데

1. 시작 인덱스

2. 종료 인덱스

이런식으로 시도해본 것이 처음이라 헷갈렸다. 

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        int [] arr = new int[n+1];
        int count =1; //15만 뽑는 경우
        int sum=1;
        int start_idx = 1;
        int end_idx=1;

        //end_idx가 n이 아닐때까지만 돌면 된다. (for 문을 하면 15번만 도니까 while로 해주어야 할 것 같다.)
        // start_idx, end_idx 필요하다.
        //sum에 end_idx를 더해준다.-> end_idx는 현재 start_idx와 같다.
        //sum이 n보다 작으면, end_idx++를 해준다.
        //sum이 n과 같으면 count++를 해주고, end_idx++를 해준다.
        //sum 이 n보다 크면, sum-start_idx를 해주고, start_idx++를 해준다. 그럼 2번째~ end_idx까지의 합이 나온다.
        //만약 여기서 sum이 n보다 작으면 다시 end_idx를 해준다.
        //이걸 end_idx가 n이 아닐때까지만 반복하면 된다.

        while(n!=end_idx){
            if(sum==n){
                count++;
                end_idx++; //범위를 넓혀주고
                sum = sum+end_idx; //넓혀준 범위만큼 sum에 더해준다.
            }
            else if(sum>n){
                sum = sum -start_idx;
                start_idx++;
            }
            else{ //sum이 n보다 큰 경우
                end_idx++; //end idx는 이미 더해져서 와서, end_idx++ 해준다. 이거 먼저 안해주면 같은값을 다시 더해주는 거임
                sum = sum+end_idx;

            }

        }


        System.out.println(count);

    }
}