[백준][C++]1253번 좋다

문제

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

1253번: 좋다

 

 

풀이

• 투 포인터 이동 원칙

  - A[i] + A[j] > K : j--;

  - A[i] + A[j] < K : i++;

  - A[i] + A[j] == K : count++; 프로세스 종료

 

투 포인터 알고리즘

투 포인터 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  vector<int> A(N);
  for(int i = 0; i < N; i++)
  {
    cin >> A[i];	// 배열 A에 데이터 저장
  }
  sort(A.begin(), A.end());	// 배열 A 정렬하기

  int count = 0;
  for(int pivot = 0; pivot < N; pivot++)
  {
    int i = 0; 
    int j = N - 1;
    
    // 투 포인터 알고리즘
    while(i < j)	
    {
      // 서로 다른 두 수의 합인지 체크
      if(A[i] + A[j] == A[pivot])	
      {
        if(i == pivot)
        {
          i++;
        }
        else if(j == pivot)
        {
          j--;
        }
        else
        {
          count++;
          break;
        }
      }
      else if(A[i] + A[j] < A[pivot])
      {
        i++;	// 포인터 i 증가
      }
      else
      {
        j--;	// 포인터 j 감소
      }
    }
  }

  cout << count;	// 좋은 수 개수 출력
  
  return 0;
}

 

 

오답

배열의 모든 수에 대하여 투 포인터 이동 원칙을 활용해 탐색을 수행한다.

⇒ 자기 자신을 좋은 수 만들기에 포함 X

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  vector<int> A(N, 0);

  for(int i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  int Result = 0;
  for(int k = 0; k < N; k++)
  {
    long find = A[k];
    int i = 0;
    int j = N - 1;

    // 투 포인터 알고리즘
    while(i < j)
    {
      // 서로 다른 두 수의 합인지 체크
      if(A[i] + A[j] == find)
      {
        if(i != k && j != k)
        {
          Result++;
          break;
        }
        else if(i == k)
        {
          i++;  
        }
        else if(j == k)
        {
          j--;
        }
      }
      else if(A[i] + A[j] < find)
      {
        i++;
      }
      else
      {
        j--;
      }
    }
  }

  cout << Result << "\n";
}