[Java/백준] 연속된 자연수의 합 구하기 #2018

문제

 

 

 

풀이

(1) 문제 분석하기

• N의 최댓값(10,000,000)이 매우 크므로 O(n)의 시간 복잡도 알고리즘 사용해야 함 → 투 포인터!
• 시작 인덱스와 종료 인덱스를 투 포인터로 지정하여 접근

 

(2) 손으로 풀어 보기

출처 : Do it! 알고리즘 코딩 테스트 - 실전문제 풀이(JAVA)

1. N값을 입력받아 변수에 저장하고, 사용할 변수(sum, count, start_index, end_index) 모두 1로 초기화
   (count를 1로 초기화하는 이유는? 연속된 수가 자기 자신인 경우를 미리 포함한 것)
2. 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구함
3. 2단계를 end_index가 N이 될 때까지 반복
   포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count를 1만큼 증가

// 투 포인터 이동 원칙
sum > N : sum = sum - start_index; start_index++
sum < N : end_index++; sum = sum + end_index;
sum == N : end_index++; sum = sum + end_index; count++;

※ 왜 시간 복잡도가 N이 될까? start_index가 N번, end_index가 N번 데이터를 훑어서 2N → 상수는 시간 복잡도 계산에서 제외되므로 N의 시간 복잡도를 갖는다!

 

(3) 슈도코드 작성하기

N 변수 저장(입력 데이터가 많지 않으므로 Scanner 사용)
사용 변수 초기화(sum, count, start_index, end_index = 1)
while(end_index != N) {
	if(sum == N) count 증가, end_index 증가, sum값 변경
    else if(sum > N) sum값 변경, start_index 증가
    else if(sum < N) end_index 증가, sum값 변경
}
count 출력하기

 

(4) 코드 구현하기

import java.util.Scanner;

public class TheSumOfNumbers2018 {

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

}

 

 

 

 

 

2018번: 수들의 합 5

 

※ 이 내용은 Do it! 알고리즘 코딩테스트 - 실전문제 풀이(JAVA) 강의를 듣고 정리한 내용입니다.