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

문제 링크 : 백준 2018번 - 수들의 합 5 자바

 

N이 주어졌을 때, 이를 연속된 자연수의 합으로 나타내면 어떻게 될까?

예시로, 15인 경우 7+8, 4+5+6, 1+2+3+4+5 와 같이 될 수 있다.

             10인 경우, 1+2+3+4 와 같이 될 수 있다.

이와 같이 연속된(2개 이상) 자연수의 배열이 나타나는 횟수를 구하면 되는 문제이다.

 

여기서 "두 포인터"라는 개념을 이용할 것이다.

먼저 start와 end 변수가 배열의 첫번째를 가리킨다. (이렇게 가리키는 것을 '포인터'라고 간단하게 말 할 수 있다. 자세한 것은 C언어 포인터에서 배우면 된다.)

그리고 start와 end 사이의 수를 더하여 N과 비교한다.

만약 합이 N과 같다면 결과 횟수를 1 늘리고, end를 1 증가시켜준다. (start를 증가시킬 순 없고, 모든 배열을 검사해봐야 하니)

만약 합이 N보다 크다면 수를 더 줄여야 하므로, start를 1 증가시켜준다. 그렇게 하면 뒤쪽에서 연속된 수의 합을 구하게 될 수도 있다.

만약 합이 N보다 작다면 수를 더 키워야 하므로, end를 1 증가시켜준다.

 

왜 start를 증가시켜주고 end를 증가시켜주는지는 아래의 예시 그림을 따라가면서 이해를 해보면 좋을 것 같다.

Q. sum > N 일때는 왜 sum에서 먼저 빼고, sum < N 일때는 왜 sum에 나중에 더하나요?

A. sum > N 일때는 크기를 줄이는 것이므로 1. 뺄 숫자를 먼저 빼고 2. 인덱스를 +1 하여 수정한다.

     sum < N 일때는 크기를 늘리는 것이므로, 1. 인덱스를 먼저 증가시켜 더할 수를 가르키고 2. sum에 더한다.

 

따로 배열을 두지 않고 변수들만 이용하여 계산할 수 있다. 참고 이미지 밑의 코드를 참고하라.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int count = 1;
        int start = 1;
        int end = 1;
        int sum = 1;

        while (end <= N/2+1) {
            if (sum == N) {
                count++;
                end++;
                sum += end;
            } else if (sum > N){
                sum -= start;
                start++;
            } else {
                end++;
                sum += end;
            }
        }
        System.out.println(count);
    }
}