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;
}
}
}
}
}
}
재귀로 풀었을 때, 어떤 실수를 범했는지 모르겠어서 질문게시판에 올려봤다. 답이 와야할텐데..
Author And Source
이 문제에 관하여(BOJ_2295), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/BOJ2259저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)