C++ ) 백준 2003 수들의 합 2

 

문제

 

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

2003번: 수들의 합 2

 

내 풀이

 

투 포인터를 사용해서 풀었다.

투 포인터란 front와 back 포인터를 설정한 후에 front와 back을 한칸씩 이동하며 조건과 부합하는지를 찾는 알고리즘이다. 

 

이 문제는 '연속하는' 수들의 합을 찾기 때문에 front와 back 사이의 모든 값들을 더한 SUM을 갱신하는 투 포인터와 알맞다고 할 수 있다.

O(1)의 시간복잡도를 가지므로 모든 가능한 경우를 다중 for문으로 찾는 것보다 훨씬 빠르다.

 

보통의 투 포인터 문제들은 조건에 부합하면 return 하지만, 이 경우에는 모든 경우들을 세어줘야 하므로 결과값을 갱신 후 front를 뒤로 보내서 다시 search하도록 했다.

 

 

 

 

 

 

내 코드

 

위 그림의 SUM을 now로 네이밍하여 구현했다.

 

#include <iostream>

using namespace std;

int Array[10000];
int result = 0;

void Slide(int N, int M)
{
  int front = 0;
  int back = 0;
  long long now = Array[0];

  while (back != N)
    {
      //cout << "front is " << front << " back is " << back << " result is " << now << endl;
      if (now == M) // 값을 찾았다면
      {
        result ++;
        now -= Array[front];
        front ++;
      }
      else if (now < M || front >= back) // front가 back을 역전하거나 같은 경우와 now가 M보다 작은 경우의 코드가 같다.
      {
        back ++;
        now += Array[back];
      }
      else // now가 M보다 크다면
      {
        now -= Array[front];
        front ++;
      }
    }
}

int main() { 
  int N, M;

  cin >> N >> M;

  for(int i = 0; i < N; i++)
    cin >> Array[i];
  Slide(N, M);
  cout << result;
  return 0;
}