본인 풀이

#include <bits/stdc++.h>
using namespace std;
int n, m, ret = 0;
int num[15000];

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

    // 고유한 번호 -> 중복문제는 아님 -> Map은 필요 없음
    // 합 문제 -> 누적합처리?
    // 1 2 3 4 5 7
    // 1 3 6 10 15 22
    // 1 3 5 7 9 12
    // 1 2 6 9
    // 1개일때 두개일때 .. 각각 누적합 처리
    //
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> num[i];
    }

    if(find(num, num + n, m)){
        ret += 1;
    }

    for (int i = 1; i < n; i++)
    {
        int psum[n];

        // 0번부터 누적합 전까지는 삽입해놓음
        for (int k = 0; k < i; k++)
        {
            psum[k] = num[k];
        }

        // 누적합 1개 조합..
        // 누적합 2개 조합..
        for (int j = i; j < n; j++)
        {
            psum[j] = psum[j - 1] + num[j] - psum[j - i];
        }

        for (int j = 0; j < n; j++)
        {
            if (psum[j] == m)
            {
                ret += 1;
            }
        }
    }

    cout << ret << "\n";

    return 0;
}

1. 못풀었음

#include <bits/stdc++.h>
using namespace std;
int n, m, ret;
vector<int> v;

void combination(int start, vector<int> b){
    if(b.size() == 2){
        if (v[b[0]] + v[b[1]] == m){
            ret += 1;
        }
        return;
    }

    for (int i = start + 1; i < n; i++){
        b.push_back(i);
        combination(i, b);
        b.pop_back();
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < n; i++){
        int num;
        cin >> num;
        v.push_back(num);
    }
    vector<int> idx;

    combination(-1, idx);
    cout << ret << "\n";

    return 0;
}

시간초과 발생

모범 답안

1. 조합을 활용하는것은 맞음. 단, 재귀로 풀 경우 시간복잡도가 더 커져서 시간초과가 발생
2. 조합 3개까지는 중첩For문으로 구현하자.

#include <bits/stdc++.h>
using namespace std;
int n, m, ret;
int a[15000];

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

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    if(m > 200000){
        cout << 0 << "\n";
    }else{
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                if(a[i] + a[j] == m){
                    ret += 1;
                }
            }
        }

        cout << ret << "\n";
    }


    return 0;
}

시간초과를 줄이기

시간초과 체크가 타이트한 문제는 무슨 수를 써서라도 소요시간을 줄여야 한다. if 200000 분기처리 코드가 이에 해당한다