문제

https://www.acmicpc.net/problem/2018

설명

위 문제는 시간 제한이 2초이기에 이중 포문으로 위 문제를 해결할 경우 입력값 천만인 일때 2억을 훌쩍 넘기기 떄문에 다른 방법으로 풀어야 된다.
주인장은 구간 합과 투 포인터를 이용하여 문제를 풀 수 있다.

구간 합

배열의 합을 구할때 시간 단축을 하기에 좋은 알고리즘 중 하나는 구간 합이다.
구간 합을 구하기 위해서는 배열의 합을 먼저 구해야 된다.

6칸이 있는 배열에 1부터 6까지 값을 들어 있는 배열 A가 있으면
새로운 배열을 만들어 인덱스 0번 A 배열부터 인덱스 5번 A배열까지의 각 합 들을 구해 새로운 배열 칸에 넣어 준다.

이렇게 합 배열이 구해지면 구간 합은 다음과 같이 이용하면 된다.

S[j] - s[i-1] // i에서 j까지의 합

이는 배열 A에서의 다음 상황과 같다.

구간의 합을 구할 시작 인덱스가 4이고 끝나는 값이 5인 경우

배열 A에서의 값은 5 + 6이며 이는 11의 결과값을 출력한다.

이를 합 배열로 구간 합을 구하면 다음과 같다.

조금 풀어서 설명하면 0번 인덱스에서 5번 인덱스까지의 합에서
0번 인덱스에서 3번 인덱스까지의 합을 빼주는 것이다. 그렇게 되면 결과값은 4번 인덱스 에서 5번 인덱스까지의 합만 남게 되는 것이다.

투 포인터

투 포인터는 계산하려는 배열의 범위나 해당 배열 값들을 이용하는 알고리즘이라고 생각하면 된다.

투 포인터 원칙

투 포인터를 사용할때는 위와 같은 규칙이 있다
(문제에 따라서는 위 규칙이 바뀌는 경우도 있으므로 유도리 있게 사용할 것)

sum = sum + endPoint or startPoint는 구간 합을 의미한다.

또한 위 규칙은 while문 안에서 돌기 때문에 while문 조건식도 상황에 맞게 사용해야된다.

풀이

입력한 값이 6인 경우 -> while(endPoint != 6)

투 포인터 규칙에 의해 sum값이 입력한 값 6보다 적으므로 endPoint를 한칸씩 증가시킨다.

투 포인터 규칙에 의해 sum값이 입력한 값 6보다 크므로 startPoint를 한칸씩 증가 시킨다.

규칙에 맞게 두 포인터를 sum의 값과 입력한 값이 맞을때까지 증가 시킨다.

sum의 값과 입력한 값이 맞으면 endPoint를 증가 시키고 cnt를 1증가 시킨다.

이렇게 while문 조건에 맞을때까지 일치한 구간을 전부 찾아낸다.

코딩

import java.util.Scanner;

public class J2018 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();
        int[] numArray = new int[num+1];
        int cnt = 0;
        int sum = 0;
        int startPoint = 0;
        int endPoint = 1;

        for(int i = 0; i <= num; i++){
            sum += i;
            numArray[i] = sum;
        }

        while(endPoint != num+1){
            if((numArray[endPoint] - numArray[startPoint]) < num)
                endPoint++;
            else if ((numArray[endPoint] - numArray[startPoint]) > num) {
                startPoint++;
            }
            else if((numArray[endPoint] - numArray[startPoint]) == num){
                cnt++;
                endPoint++;
            }
        }

        System.out.println(cnt);
    }
}