[백준 | JAVA | 2018번] 수들의 합 5

 

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

 

📝 유튜브 풀이

https://www.youtube.com/watch?v=ZovjkF2DzIs&list=PLFgS-xIWwNVU_qgeg7wz_aMCk22YppiC6&index=5

• N의 최댓값이 크기 때문에 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 시간 제한을 초과하므로 O(n)의 시간복잡도 알고리즘을 사용해야함.
  → 이 때 투포인터 사용
• 시작인덱스와 종료 인덱스를 지정하여 연속된 수를 표현

1. 시작과 종료 인덱스를 맨 앞자리에 둔다.
   초기화 sum =1 count =1
   sum : 시작 인덱스와 종료 인덱스가 갖는 연속된 합의 크기
   count : 연속된 수의 케이스 ( 숫자 그 자체 (N 그자체) 가 될 수 있기 때문에 미리 저장하여 1로 초기화)

1. 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다.
   시작 인덱스가 오른쪽으로 한 칸 이동 하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며,
   종료 인덱스가 오른쪽으로 한 칸 이동 하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미
   같을 때에는 경우의 수를 1 증가시키고 종료 인덱스를 오른쪽으로 이동

투 포인터 이동 원칙

• sum > N : sum = sum - 시작 인덱스 ; 시작인덱스 ++;
• sum < N : 종료 인덱스 ++; sum = sum + 종료 인덱스 ;
• sum == N : 종료 인덱스 ++; sum = sum + 종료인덱스 ; count ++;

import java.util.*;

public class Main {

    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		
		int count =0;
		int start_index = 1;
		int end_index = 1;
		int sum =1;
		
		while(end_index != N) {
			if(sum==N) {
				count++;
				end_index++;
				sum += end_index;
			} else if(N<sum) {
				sum -= start_index;
				start_index++;
			} else if (sum<N) {
				end_index++;
				sum += end_index;
			}
		}
		System.out.println(count);
	}
}

 

📝 나의 풀이

import java.util.*;

public class Main {

    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		int answer = 0;
		
		for(int i=1; i<=N; i++) {
			int sum =0;
			
			for(int j=i; j<=N; j++) {
				sum+=j;
				
				if(N<sum) {
					break;
				} else if (sum==N) {
					answer++;
					break;
				}
			}
		}
		System.out.println(answer);
	}
}