투포인터 알고리즘

문제

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

2018번: 수들의 합 5

입력된 수를 연속된 수들의 합으로 나타낼 수 있는 가짓수를 출력하는 문제이다.

 

이 문제 에선 투포인터 알고리즘이 들어간다.

입력된 수가 7일 때 1 ~ 7까지의 숫자를 순서대로 놓는다.

start index와 end index를 각각 1로 두고,

count = 1 // 연속된 수들의 합으로 나타낼 수 있는 가짓수

sum = 1 // 수들의 합

으로 둔다.

count를 1로 두는 이유는 자기 자신을 미리 포함해두기 위해서 이고,

sum을 1로 둔 이유는 처음 시작이 1이기 때문이다.

 

그 다음 반복분 안에 if 문을 3개로 나눠서 

입력한 수에는 세 가지 경우의 수

1. 입력한수 < sum : sum -= start index; start index++;

2. 입력한 수 == sum : count++; end index++; sum += end index;

3. 입력한 수 > sum : end index++; sum += end index;

로 나눠서 수행하는 알고리즘이다.

 

투포인터 개념 쉽다고 하는데 개인적으로 이해가 잘 안되고 어렵다.....ㅠㅠ

이 알고리즘은 직접 그림으로 보면 이해가 잘된다.

 

<7을 입력했을 때 풀이>

처음

입력한 수(7)가 sum(1)보다 클 때는

end index를 앞으로 한 칸 옮기고,

sum에다 + end index를 한다.

이 걸 4번 반복하면

이렇게 되고 sum = 10이 된다.

입력한 값(7) < sum(10) 이므로,

sum에서 start index값을 빼고,

start index를 앞으로 한 칸 옮긴다.

sum이 아직 9이므로 이 행동을 한 번 더한다.

 

그렇게 하면 sum이 7이되고, sum 과 입력한 수(7) 이 같아진다.

이럴 때 count에다 +1을 해주고, end index에다 +1을 해준다.

그리고 sum에다 + end index를 해서

계속 반복한다.

 

구현 코드

코드 출처 : https://github.com/doitcodingtestjava/answer

import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    
    int count = 1;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;
    
    while (end_index != N) {
      if (sum == N) {         //sum == N ->  End index++;  sum = sum + End index;  count++;  
        count++;
        end_index++;
        sum = sum + end_index;
      } else if (sum > N) {   //sum > N ->  sum = sum - Start index;  Start index++;
        sum = sum - start_index;
        start_index++;
      } else {                //sum < N ->  End index++;  sum = sum + End index;
        end_index++;
        sum = sum + end_index;
      }
    }
    System.out.println(count);
  }
}