[Baekjoon 백준] 2018 수들의 합 5 - Java

문제) 어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

---

1. 변수 선언

2. 합계 값에 따라 시작 인덱스, 종료 인덱스 조정

 

public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/baekjoon/code2018"));
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 제시된 정수(1 ≤ N ≤ 10,000,000)
		int sum = 1; // 합
		int count = 1; // 개수
		int startIndex = 1; //시작 인덱스
		int endIndex = 1; //종료 인덱스
		
		while(endIndex != N) {
			if(sum == N) {
				count++;
				endIndex++;
				sum = sum + endIndex;
			}
			else if(sum > N) {
				sum = sum - startIndex;
				startIndex++;
			}
			else {
				endIndex++;
				sum= sum + endIndex;
			}
		}
		System.out.println(count);
	}

 

문제에 주어진 제한 시간은 2초, N의 최댓값은 10,000,000으로 매우 크다.

이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로

O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 접근.

 

count를 1로 초기화 하는 이유는 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 넣고 초기화하기 위함이다.

sum = N 인 경우 count와 종료 인덱스를 증가시키고, sum = sum + endIndex

sum > N 인 경우 시작 인덱스를 증가시킨다.  sum = sum - startIndex

sum < N 인 경우 종료 인덱스를 증가시킨다.  sum = sum + endIndex