Baekjoon 2003 수들의 합 2 - 투 포인터

2003번: 수들의 합 2

투 포인터에 대한 문제이다.

N의 최대값이 10000이라 2중 for문으로 해도 정답이다.

1. 포인트는 start와 end 두개!

int end = 0;
int start = 0;
int sum = 0;

2. sum이 M과 같아진다면 end 증가

for(; start < N ; ++start) {
  sum += numbers[start];
  if(sum == M) {
    answer++;
    sum -= numbers[end++];
  } else if()
  // 3. sum이 M보다 크다면
}

3. sum이 M보다 크다면 sum이 M보다 작아질 때까지 end 증가

 else if(sum > M) {
    while(sum > M) {
      sum -= numbers[end++];
      if(sum == M) {
        answer++;
        break;
      }
    }
  }

start 포인트를 움직이다가 어떠한 상황이 왔을 때 end 포인트를 움직이는 알고리즘을  "투 포인터" 라고 한다.

 

비슷한 문제

1644번: 소수의 연속합