[백준] 2018번: 연속된 자연수의 합 구하기 - JAVA

 

 

✍️풀이방식

 

투 포인터를 활용해서 풀기 O(n)의 시간복잡도 알고리즘 사용할 것 

* 입력되는 연산 수가 많으면 꼭 시간복잡도를 생각해서 관련 알고리즘을 적용시켜야합니다. 

 

 

 

투 포인터 알고리즘이란? 

 

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘


1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다. (strat, end) 
2. 현재 부분 합이 M과 같다면 count
3. 현재 부분 합이 M보다 작다면 end를 1 증가 
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복 

 

 

 

 

 

 

 

 

투 포인터 관련 개념 참고하였습니다. 

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

 

 

---

 

 

🖥️문제풀이

 

이번 문제는 데이터 입력양이 적기 때문에 scanner로 구현

 

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException {
	    Scanner sc = new Scanner(System.in);
	    int N =sc.nextInt();
	    int start_index=1;
	    int end_index=1;
	    int count=1;
	    int sum=1; 
	    while(end_index!=N){
	        if(sum==N){
	            count++;// 일치하면 카운트 증가
	            end_index++;
	            sum += end_index;
	        }else if(sum>N){
	            sum -=start_index;
	            start_index++;
	        }else{//sum이 n보다 작을 때 
	            end_index++;
	            sum += end_index;
	        }
	        
	    }
	    
	    System.out.println(count);
	    
	}
}

 

 

 

 

 

 

 

 

 

 

☑️실행결과