글 읽기 - 좀 다른 방식으로 풀었는데 어디가 잘못됬을까요?

simsimjae 3년 전 0

풀이 방법은 우선 들어온 수들을 정렬합니다 O(nlogn)이기 때문에 무리없을거라 생각했구요

그리고 나서 모든 연속된 수들의 부분합을 계속 구하는 2중 for문을 사용했습니다. 문제 n조건이 크기 때문에 O(n2)으로는 풀리지 않는것을 알고있습니다. 하지만, 배열의 끝부분까지 모두 합을 구했는데도 s보다 작다면 더 진행해봐야 s보다 큰 수가 나오기 힘드니까 그냥 break;시키는 식으로 반복을 줄였습니다(정렬 되있으므로)

3%정도에서 틀리길래 풀이를 봤는데 제 풀이랑 비슷한거 같으면서도 뭔가 다르네요. 풀이를 이해하긴 해서 문제를 풀 수 있을거 같긴 한데 제 방법이 왜 틀렸는지를 알고 싶습니다. 고수분들 답변 부탁드립니다!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, s;
vector<int> v;

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		int temp; scanf("%d", &temp);
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	int size = v.size();
	int len = 99999999;
	for (int i = 0; i < size; i++) {
		int sum = 0;
		bool chk = false;
		for (int j = i; j < size; j++) {
			sum += v[j];
			if (sum >= s) {
				len = min(len, j - i + 1);
				chk = true;
				break;
			}
		}
		if (!chk && i == 0)
			len = 0;
		if (!chk) 
			break;
		
	}
	cout << len << endl;
	return 0;
}

jung2381187 3년 전 1

주어진 수열의 순서를 바꾸면 안 됩니다.

simsimjae 3년 전 0

아.. 정렬하는순간 경우의수가 달라지겠네요 감사합니다 !

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

문제

문제

출처

ICPC

좀 다른 방식으로 풀었는데 어디가 잘못됬을까요?

simsimjae 3년 전 0

jung2381187 3년 전 1

simsimjae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말