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

입출력 예시

Input
15
Output
4

문제 풀이

---

이 문제는 주어진 n의 최댓값이 10,000,000이기에 빠른 시간복잡도를 가진 알고리즘으로 풀어야 한다.
연속된 자연수들의 합을 시작 인덱스(start_idx)와 종료 인덱스(end-idx)를 지정하여 표현해보자.

투 포인터 활용(시작인덱스와 종료인덱스)

먼저 입력받을 n과 사용할 변수들을 초기화하자.
start_idx와 end_idx의 경우 1부터 n까지 탐색할 것이기에 1로 초기화한다.
그리고 cnt를 1로 초기화한 이유는 n 자신도 연속된 자연수들의 합 케이스에 포함된 것으로 간주하여 1로 초기화하였다.
sum은 시작인덱스와 종료인덱스별로 더하거나 뺄 변수로 활용되고, 1부터 시작하기에 1로 초기화한다.

int n = Integer.parseInt(br.readLine());
int start_idx = 1;
int end_idx = 1;
int cnt = 1;
int sum = 1;

투 포인터를 활용해 연속된 자연수들의 합을 어떻게 구할 것인가?
아래 공식을 활용해 구할 수 있다.

• sum이 n보다 작다면, end_idx++하고, sum에 end_idx를 더한다.
• sum이 n보다 크다면, sum에서 start_idx를 빼고, start_idx++한다.
• sum이 n과 같다면, cnt++, end_idx++, sum에 end_idx를 더한다.

n이 15일 때 경우를 예로 들어보자.

start=1, end=1, sum=1 -> sum<15
    end+1 = 2
    sum+end = 3
start=1, end=2, sum=3 -> sum<15
    end+1 = 3
    sum+end = 6
start=1, end=3, sum=6 -> sum<15
    end+1 = 4
    sum+end = 10
start=1, end=4, sum=10 -> sum<15
    end+1 = 5
    sum+end = 15
start=1, end=5, sum=15 -> sum==15
    cnt+1 = 2
    end+1 = 6
    sum+end = 21
start=1, end=6, sum=21 -> sum>15
    sum-start = 21-1 = 20
    start+1 = 2
start=2, end=6, sum=20 -> sum>15
    sum-start = 20-2 = 18
    start+1 = 3
start=3, end=6, sum=18 -> sum>15
    sum-start = 18-3 = 15
    start+1 = 4
start=4, end=6, sum=15 -> sum==15
    cnt+1 = 3
    end+1 = 7
    sum+end = 22
...

위와 같은 방식으로 end_idx가 15가 될 때까지 반복하며 sum이 15와 같을 때마다 cnt를 증가시킨다.

위 공식을 코드로 작성해보자.

while(end_idx != n) {
    if(sum == n) {
        cnt++;
        end_idx++;
        sum+=end_idx;
    }
    else if(sum > n) {
        sum-=start_idx;
        start_idx++; 
    }
    else if(sum < n) {
        end_idx++;
        sum+=end_idx; 
    }
}

while문에서 end_idx가 n이 될때까지 순회하며 sum==n일 때, sum>n일 때, sum<n일 때 조건문을 통해 연속된 자연수들의 합이 몇가지인지 구할 수 있다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int start_idx = 1;
        int end_idx = 1;
        int cnt = 1;
        int sum = 1;
        
        while(end_idx != n) {
            if(sum == n) {
                cnt++;
                end_idx++;
                sum+=end_idx;
            }
            else if(sum > n) {
                sum-=start_idx;
                start_idx++; 
            }
            else if(sum < n) {
                end_idx++;
                sum+=end_idx; 
            }
        }

        bw.write(cnt+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 프로그래머스의 숫자의 표현 문제와 동일한 문제지만, 이 문제는 주어진 n의 최댓값이 10,000,000으로 매우 크게 잡혀있기 때문에 O(n)의 시간복잡도 알고리즘을 활용해야 했다.
• 투 포인터를 활용해 연속된 자연수들의 합을 구하면서 시작인덱스와 종료인덱스를 활용하는 과정을 공부할 수 있었다.