BOJ_2295

😳 처음에 내림차순 배열을 만든 뒤, 재귀 중복조합함수를 사용하여 풀어내려했는데, 어디서 오류가 생겼는지 자꾸 틀렸다고 뜬다... 그래서 3중 for문으로 조합을 대체.

2295 : 세 수의 합

• x, y, z, k 로 수를 만들 때, k의 수가 최대 값이 되도록 만들어줘야 함.
• 그렇기에 배열을 오름차순으로 만들고 작은 수부터 세 수를 더해가면 4중 for문일 때, 시간초과가 날 수밖에 없음.
• 그래서 배열을 내림차순으로 정렬해주고, 큰 세 수부터 더해가며 구하는 즉시 코드를 종료하는 식으로 진행.

💻 4중 for문

for (int i = 0; i < n;i++)
    {
        int stand = arr[i];
        int x, y, z;
        for (int j = i + 1; j < n;j++)
        {
            x = arr[j];
            for (int k = j; k < n;k++)
            {
                y = arr[k];

                if(x+y>stand)
                    continue;
                for (int t = k; t < n;t++)
                {
                    z = arr[t];
                    if(x+y+z ==stand)
                    {
                        cout << stand << endl;
                        return 0;
                    }
                }
            }
        }
    }

• stand 값에 배열의 가장 큰 수부터 담으며, for문을 진행.

• set 값을 사용해서 만들어도 괜찮을 것 같다.

• 잘 보면 k, t의 값이 앞의 수를 그대로 따라가는 for문이다.

• 이는 중복조합이기에 그대로 넣어주는 것.

• 만약 중복조합이 아니라면 k는 j+1, t는 k+1 이런식으로 풀어줘야 할 것.

• 중간 중간에, if(x+y>stand)와 같이 예외 사항에 대해서 continue 시켜줬다.

  💻 전체 코드

 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <string.h>

using namespace std;

#define endl "\n"
typedef long long ll;

bool compare(ll a, ll b)
{
    return a >= b;
}

int arr[1001];

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

    int n;

    cin >> n;

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

    sort(arr, arr + n, compare);

    for (int i = 0; i < n;i++)
    {
        int stand = arr[i];
        int x, y, z;
        for (int j = i + 1; j < n;j++)
        {
            x = arr[j];
            for (int k = j; k < n;k++)
            {
                y = arr[k];

                if(x+y>stand)
                    continue;
                for (int t = k; t < n;t++)
                {
                    z = arr[t];
                    if(x+y+z ==stand)
                    {
                        cout << stand << endl;
                        return 0;
                    }
                }
            }
        }
    }
}

재귀로 풀었을 때, 어떤 실수를 범했는지 모르겠어서 질문게시판에 올려봤다. 답이 와야할텐데..