[백준/c++] 1253번: 좋다

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

1253번: 좋다

 

문제 요약

 

N개의 수 중 다른 수 두 개의 합으로 나타낼 수 있는 수 = 좋다(GOOD)

N개의 수 중 좋은 수의 개수는? (수의 위치가 다르면 값이 같아서 다른 수)

 

범위

 

수의 개수 N(1 ≤ N ≤ 2,000)

 

i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, 정수)

 

 

---

 

다른 수 두 개의 합으로 나타낼 수 있는 수의 개수를 세야 하므로, 반복문을 통해 전체 배열 속 원소에 대해 계산해봐야 한다. 각 원소의 인덱스를 함수의 매개변수로 넘겨서 합이 해당 원소 값이 되는 것을 구하면 된다. 그전에 정렬을 먼저 해준다. (정렬을 하면 합이 해당 값(x) 보다 크면 그 뒤로는 계산을 하지 않아도 되기 때문)

 

L과 R 두 포인터를 사용해서 두 수를 더하면 되는데,

• L과 R을 나란히 두고 R을 전진하면서 하는 것
  
  
• L과 R을 양끝에 두고 가운데로 모이게 하는 것

 

첫 번째 방법은 모든 원소를 돌게 되므로 연산을 많이 하게 된다.(두번째 방법에 비해) 또한 다음 L 케이스에서 R의 값을 변경해줘야 한다.

양 끝에 두고 가운데로 이동하도록 하면 L과 R을 우리가 원하는 값에 맞춰서 이동하게 된다. 두 번째 방법이 더 효율적이다.

 

여기서 놓치면 안되는 것이 있는데, 두 수를 선택할 때 자신이 포함되면 안 된다는 것이다. 문제에서 분명 "다른 수 두 개의 합"이라고 했기 때문이다. 그러므로 만약 L 혹은 R이 가리키는 원소와 자신이 동일하다면 L 혹은 R의 위치를 이동시킨다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[2002], cnt=0;

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
}

void cal(int index){
    int x = a[index];
    int R = n, L = 1;
    while(L<R){
        if(L == index) L++;         //자기 자신은 덧셈에 포함 안됨
        else if(R == index) R--;    //자기 자신은 덧셈에 포함 안됨
        else{
            if(a[L] + a[R] < x) L++;                        //값이 더 커져야 하므로 작은 값(L)을 증가
            else if(a[L] + a[R] == x) {cnt++; return;}      //합이 x이므로 카운팅
            else R--;                                       //값이 더 작아져야 하므로 큰 값(R)을 감소
        }
    }
}

void solution(){
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) cal(i);
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!