[Java] 백준 2810 수들의 합 5 (자료구조1,투포인터)

 

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

2018번: 수들의 합 5

 

[문제분석]

연속된 수를 더해야 하므로 합배열을 이용할 수도 있지만

입력값이 1~10,000,000 이므로 시간초과 될 수도 있음.

따라서 시간복잡도를 줄일 수 있는 투포인터를 사용

 

---

[진행순서]

1. 투포인터 로직 작성

    1-1 연속합, 시작index, 끝index, 정답 선언

    1-2 연속합이 입력값 N 과 같으면 정답+1, 연속합, 끝index 변경

    1-3 연속합이 입력값 N 보다 크면 연속합, 시작index 변경

    1-4 연속합이 입력값 N 과 작으면 연속합, 끝index 변경

 

 

import java.util.Scanner;

public class Main {

    /*
    * 백준 2018번 수들의 합 5
    * N(1~10,000,000)을 입력받아 연속된 자연수의 합으로 나타내는 가짓수 출력하기
    * 15 > 4개
    * 15  7+8  4+5+6  1+2+3+4+5
    * 10 > 2개
    * 10  1+2+3+4
    * */
    /*
    * 입력데이터
    * 15
    * 출력데이터
    * 4
    * */

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int 입력 = sc.nextInt();
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int 연속합 = 1;

        while (end_index != 입력){
            if (연속합 == 입력){
                count++;
                end_index++;
                연속합 += end_index;
            }else if (연속합 < 입력){
                end_index++;
                연속합 += end_index;
            }else if (연속합 > 입력){
                연속합 -= start_index;
                start_index++;
            }
        }
        System.out.println(count);
    }
}

 

+ 문제풀이 예시

입력 5

출력 2