💚 백준 2018 수들의 합 5

1. 문제 분석

문제 링크

1~N까지 수 중에서 연속된 합으로 N이 나올 수 있는 가짓수 구하기

시간 제한 2초, 주어지는 N의 최대값 10,000,000
무엇을 최적화라 말하는지 아직 모르겠어서, 이것들의 의미가 와닿지 않는다.

2. 푸는 원리

투포인터로 풀기

1. 연속된 수들의 합을 축척한 변수 acc를 만든다.
2. 오른쪽 포인터 b가 움직일 때마다, acc 에 b 만큼 더한다.
3. 왼쪽 포인터 a가 움직일 떄마다 acc에서 a 만큼 뺀다.
4. 특정 시점에서 acc의 값이 N과 같아졌을 경우, N이 되는 가지수를 하나 센다.

문제 푸는 방법은 생각났지만, 세부적으로 a와 b를 acc에 더하는 시점, while 문을 끝내는 시점 등에서 많이 해매서, 답지를 봤다.
a와 b가 현재 존재하는 index 부분은 acc에 더해진 부분이라는 것을 기준으로 생각하니 이해 되었다.

b는 현재 값이 아닌 값 (그 다음 값)을 더해야 하므로, b++ 로 이동한 뒤 더한다.

a는 현재 값 자체를 빼야 하므로 a를 뺴고 이동한다.

b == N이면 loop를 종료한다. 이유는 선봉 대장인 b == N이 되는 순간 구간합은 무조건 N보다 커지기 때문에, 그 이후는 상정할 필요가 없다.

3. 코드 분석

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


/*
 * 2018번 수들의 합 5
 * */


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());


        // a    -> 왼 pointer, b -> 오 포인터, acc  -> 축적값
        // cnt  -> N = N 즉 자기 자신으로 구간합이 되는 경우는 미리 세고 간다.
        int a = 0, b = 0, acc = 0, cnt = 1;

        // 오른쪽 포인터가 N이 되는 순간 구간합은 무조건 N보다 커진다. 그래서 셀 필요가 없다.
        while (b != N) {

            if(acc < N){
                b++;
                acc +=b;
            }

            else if(acc == N) {
                cnt ++;
                b ++;
                acc += b;
            }

            else {
                acc -= a;
                a++;
            }
        }

        System.out.println(cnt);

    }
}