[백준 1253] 좋다 (C++)

문제 링크: www.acmicpc.net/problem/1253

1253번: 좋다

1. 주의할 점

- 원하는 숫자가 idx번째에 있다면, 서로 다른 두 수는 idx를 사용하여 만들어지면 안된다. 문제 설명이 모호하게 되어있다

3
0 0 3 
-> 답: 0

 

2. 구현

- 투 포인터를 이용하여 풀이한다

- 입력 받은 수들을 오름차순으로 정렬하여 투포인터의 필요조건을 만족시킨다

- 0~N-1까지 모든 수에 대해 이분탐색을 수행한다

- Left는 0, Right는 N-1부터 수행한다

- 두 수가 같으면 안되므로 Left<Right의 조건을 만족할때만 While문을 수행한다

- Arr[Left] + Arr[Right]를 Sum, Arr[idx]를 Val이라고 가정한다

- Sum < Val인 경우, 더 큰 수를 더해야 하므로 Left++

- Sum > Val인 경우, 더 작은 수를 더해야 하므로 Right--

- Sum == Val인 경우, Left와 Right이 전부 idx가 아니라면 Result++하고 While문을 종료한다. 만약 Left가 idx와 같다면 Left++을, Right이 같다면 Right--를 통해 다른 수를 사용해도 Sum과 같은지 확인한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[2000];

int main() {
    int num,result=0,val;
    cin>>num;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    sort(arr,arr+num);

    for(int i=0;i<num;i++){
        val = arr[i];     //찾고자 하는 번호
        int l=0,r=num-1,sum;
        while(l<r){
            sum = arr[l]+arr[r];
            if(sum==val){ 
                if(l!=i && r!=i){
                    result++;
                    break;
                }
                else if(l==i) l++;
                else if(r==i) r--;
            }
            else if(sum<val) l++;
            else r--;
        }
    }
    cout<<result;
    return 0;
}