글 읽기 - 반례가 잘 떠오르질 않아서 질문드립니당

gktgnjftm 5년 전 0

우선 질문검색에 있는 반례는 돌려보았는데, 잘 나오고 잘 찾지를 못하겠어서 질문올립니다

입력받은 배열을 먼저 정렬한뒤에

맨처음값을 다음값이랑 합치면서, 뒤에 모든 수를 묶는 경우

맨처음값을 합치지 않고, 그다음값부터 그다음수를 묶는 경우

1,2번째값을 합치지 않고, 그다음값부터 그다음수를 묶는 경우 ...

1,2,3...n값을 합치지 않는 경우

총 n+1가지의 경우의 수를 hab 벡터에 저장한다음에 모두 따져봤습니다.

잘 모르겠습니당 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
typedef long long ll;
vector<int> v;
vector<vector<int>> hab;
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int num;
		scanf("%d", &num);
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	hab.resize(n + 1);
	for (int i = 0; i < v.size(); i++){
		for (int k = 0; k < i; k++) {
			hab[i].push_back(v[k]);
		}
		for (int j = i; j < v.size();) {
			int next = j + 1;
			if (next<=v.size()-1){
				int gob = v[j] * v[next];
				hab[i].push_back(gob);
			}
			else {
				int gob = v[j];
				hab[i].push_back(gob);
			}
			j += 2;
		}
	}
	ll Max = 0;
	for (int i = 0; i < hab.size(); i++) {
		ll sum = 0;
		for (int j = 0; j < hab[i].size(); j++) {
			sum += (ll)hab[i][j];
		}
		Max = max(Max, sum);
	}
	printf("%lld\n", Max);
	return 0;
}

k5nen 5년 전 1

음수가 몇개 들어있으면 어떤 일이 생길까요? 음수 두개를 곱하면 이득을 볼 수 있기 때문에 양수와 음수를 따로 관리해줘야 합니다.

6
1
2
3
-1
-2
-3

Output: 11
Correct answer: 12

gktgnjftm 5년 전 0

다시생각해서풀어봤습니다 반례감사합니다ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 잘 떠오르질 않아서 질문드립니당

gktgnjftm 5년 전 0

k5nen 5년 전 1

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말