[c++] BOJ 1253 :: 좋다

문제

좋다 문제 바로가기

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

풀이

처음에 생각했던 방법은 주어진 숫자들을 for문 3중으로 돌면서 두 수의 합으로 표현할 수 있는 지 찾는 방법이다. 입력이 크지 않아서 가능할 것이라 생각하였고 해당 방법을 사용할 경우 찾으려는 숫자보다 작은 수들만 고려하면 된다고 생각하였다. 하지만 문제에서 음수까지 범위에 들어가므로 target이 된 수보다 큰 수에 음수가 더해져서 target인 수를 만들 수도 있다.

따라서 어차피 입력이 10^3 밖에 되지 않으니 주어진 숫자들 중 2개씩 골라서 더한 합을 저장하는 방식으로 구현하였다.

위와 같은 방식으로 구현하다보면

1. 같은 숫자 2개를 더하면 안된다.
2. 본인을 제외한 다른 수의 합으로 표현해야 한다.

는 조건이 걸린다. 1번은 for(int i=0; ...){ for(int j= i+1; ...) }로 구성함으로써 i, j가 겹치지 않게 만들면 쉽게 해결된다.

2번을 해결하기 위해 처음에는 0과 더해지는 수는 제외하는 방식으로 구현하였다. 하지만 이러면 1 0 1이라는 입력에서 문제가 된다. index 0의 1을 만들기 위해 0과 index2의 1이 더해질 수 있는데, 0이 더해진다는 이유만으로 제외하게 되면 해당 입력에서의 결과 값은 0이 되므로 틀린다.

결국 주어진 숫자들(numbers) 중 특정 숫자(numbers[i])가 두 수의 합으로 표현되는 지 보려면, 기존에 저장해둔 합 모음(sum) 뿐만 아니라 숫자를 만든 요소 중 i번째 숫자가 있는 지까지 파악해야 하는 것이다. 이를 단순하게 생각하면 sum에 숫자를 만든 요소를 모두 저장하는 식으로 해결할 수 있지만 시간이 너무 오래 걸린다.

해결책은 다음과 같다. 처음 numbers 들을 받을 때 sum에 미리 i라는 인덱스를 적어두면 된다. 1 0 1의 경우 1이 index 0과 2에서 나타났기 때문에 sum[1] = 0 도 되고 sum[1] = 2도 된다. 후자의 경우로 진행되었다고 가정해보자. 나중에 index 0의 1을 만드는 다른 두 수를 구할 때, index 2가 sum[1]에 등록되어있으므로 만들 수 없다. 하지만 index 0이 sum[1]에 등록되어있지 않으므로 index 0과 index 1의 조합으로 해당 숫자를 만들 수 있으니 좋은 수로 판명된다. 따라서 같은 수가 여러 개 있더라도 하나의 index만 등록되어있으면 제대로 답이 구해진다.

 

테스트 케이스

3
0 0 0
// 답 : 3

3
1 0 1
// 답 : 2

 

코드

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

using namespace std;

int main() {
    ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    // 음의 정수도 가능

    int N; cin >> N;
    vector<int> numbers;
    map<int, pair<bool, int>> sum; // 합, 좋은 수 여부, 자기자신의 idx (idx가 두 개 이상이면 어차피 하나는 들어가게 되어있음)
    // 좋은 수 여부를 저장해놔야 find를 안 쓰고 시간을 절약할 수 있음

    for (int i = 0; i < N; i++) {
        int tmp; cin >> tmp;
        numbers.push_back(tmp);
        sum[tmp] = { false, i };
    }

    if (numbers.size() < 3) {
        cout << 0;
        return 0;
    }

    for (int i = 0; i < numbers.size(); i++) { // 같은 수 2개 제외
        for (int j = i + 1; j < numbers.size(); j++) {
            int total = numbers[i] + numbers[j];

            if (!sum.count(total)) continue; // 없으면 틀렸습니다. => 이미 있으면 그냥 넘어가기
            if ((sum[total].second == i) || (sum[total].second == j)) continue; // 자기 자신 제외

            mine[total].first = true;
        }
    }

    int result = 0;
    for (int i = 0; i < numbers.size(); i++) {
        if (sum[numbers[i]].first) {
            result++;
        }
    }

    cout << result << '\n';
}