[백준 2018] 투 포인터 - JAVA

문제

어떠한 자연수 N은 하나 이상의 연속된 자연수의 합으로 나타낼 수 있다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다.반면, 10을 나타내는 방법은 10, 1+2+3+4+이다. 자연수 N(1 <= N <= 10,000,000)이 주어졌을 때,N을 연속된 자연수의 합으로 나타내는 가짓수를 출력하게 하라.

1번째 줄에 자연수 N이 주어진다.

 

문제 분석

1. 시간복잡도 분석으로 사용할 알고리즘의 범위 줄이기

 -> 2초 내에 N은 최대 10,000,000이다. O(nlogn)은 초과. O(n) 적합

2. 연속된 자연수를 구하는 알고리즘에 적합

3. 시작 인덱스, 종료 인덱스를 지정

 

공식

1. 투 포인터 이동 원칙

startIndex가 오른쪽으로 이동하면 연속된 자연수 중 왼쪽 값 삭제 (sum 줄어듦)

sum > N :
sum - startIndex; startIndex++;

 

endIndex가 오른쪽으로 이동하면 연속된 자연수 한개 더 추가 (sum 늘어남)

sum < N :
endIndex++; sum += endIndex;

 

sum과 N이 동일하면 경우의 수 카운트 증가, 다음 구간 준비

sum == N :
cnt++; endIndex++; sum += endIndex;

 

---

pseudo code 작성하기

N(자연수) 입력받기
사용 변수 초기화 (startIndex, endIndex, sum, cnt = 1)    //N 단독 자체도 N과 동일하기 때문에 cnt++ 해서 초기화

while (endIndex != N) {
    // 정답일 때
    if (sum == N) cnt ++; endIndex++; sum += endIndex;

    // 정답보다 클 때
    if else (sum > N) sum -= startIndex; startIndex++;

    // 정답보다 작을 때
    else (sum < N) endIndex++; sum += endIndex;
}

결과 출력

 

 

code

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int cnt = 1;
int startIndex = 1;
int endIndex = 1;
int sum = 1;

while (endIndex != N) {
    if (sum == N) {
        cnt++;
        endIndex++;
        sum += endIndex;
    } else if (sum > N){
        sum = sum - startIndex;
        startIndex++;
    } else {
        endIndex++;
        sum += endIndex;
    }
}

 

---

결과 확인

입력	출력
15	4