연속된 자연수의 합구하기 [투포인터] / 백준 2018

문제

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

 

 

 

 

풀이

우선 문제에 주어진 시간 제한은 2초입니다. 이런 상황에서 O( nlogn ) 의 시간 복잡도 알고리즘을 사용하면 제한시간을 초과하므로 O( n )의 시간복잡도 알고리즘을 사용해야 합니다. 이런 경우 자주 사용하는 방법이 투포인터 입니다.

※ O ( n ) : 주어진 데이터 크기 n 만큼 연산횟수가 필요한 시간복잡도

 

연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현 하겠습니다. 

 

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class 연속된자연수의합_투포인터_2018 {

    public static void main(String[] args) {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int N = Integer.parseInt(br.readLine());

            int count = 1;
            int start_index = 1;
            int end_index = 1;
            int sum = 1;

            while (end_index != N) {    // end_index가 N이 되는 순간 while 반복문이 끝나서 자기 자신인 숫자일때의 count++를 할수 없으니 count에 미리 1을 넣어줬음
                if (sum == N) {
                    count++;
                    end_index++;
                    sum = sum + end_index;
                } else if (sum > N) {
                    sum = sum - start_index;    // sum이 N 값을 넘어 버렸으니까 왼쪽 인덱스를 오른쪽으로 한칸 옮기면서 start_index값을 빼준다
                    start_index++;
                } else if (sum < N) {
                    end_index++;
                    sum = sum + end_index;
                }
            }

            bw.write(count+"");
            bw.flush();
            bw.close();

        } catch (Exception e) {
            e.printStackTrace();
        }

    }
}

 

 

 

---

출처

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94&unitId=148341&tab=curriculum