글 읽기 - 연속된 원소의 합으로 이루어진 집합을 배열에 어떻게 담을 수 있을까요

dydsj0920 6년 전 0

문제 조건처럼 연속된 원소의 합으로 이루어진 집합을 벡터나 배열에 담고 싶은데..

짱구를 이리저리 굴려도 아이디어가 안떠오르네요..

비트마스크를 써야하나 싶은데...어떻게 해야할까요?

hea1432 6년 전 1

제 코드가 깔끔한 코드는 아니지만 일단 작동은 해서 올립니다.

저는 부분집합간의 법칙을 찾아서 DP 방식으로 모든 부분집합을 생성하고

생성된 부분집합 배열중에서 목표한 값 이하의 값만 다른 vector에 저장하는 방식을 통해 문제를 풀었습니다.

처음에는 3중 for문을 통해서 모든 부분집합을 탐색했지만, 3중 for문을 사용할 경우 시간이 초과되기 때문에 이러한 방식을 적용하였습니다.

vector<int>A_set;
	vector<int>A_set2;

	int sum=0;
	for (int j = 0; j < A_count; j++){ // 원소가 1개인 부분집합 생성
		A_set.push_back(A[j]);
		sum += A[j]; // 모든 원소를 포함하는 부분집합은 원소가 한개이므로 별도로 생성
	}
	for (int i = 0; i < A_count-2; i++){ // 원소가 1개일때와 전체를 포함하는 것을 제외하고 원소개수가 2~N-1 인 부분집합 생성
		for (int j = 0; j < A_count; j++){ // 순서가 정해져 있을때 2 ~ N-1개의 원소를 가지는 부분집합은 N개가 존재한다.
			A_set.push_back(A_set[i*A_count+j] + A_set[(j+i+1)%A_count]);
		}
	}
	A_set.push_back(sum); // 원소가 N개인 경우의 부분집합은 1개 존재
	A_set.push_back(0); // 원소가 0개인 부분집합은 0개 존재
	
	for (int i = 0; i < A_set.size(); i++){
		if (A_set[i] <= target){
			A_set2.push_back(A_set[i]);
		}
	}

dydsj0920 6년 전 0

답변을 이제 봤네요. 답변 감사합니다!

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

문제

문제

출처

ICPC

연속된 원소의 합으로 이루어진 집합을 배열에 어떻게 담을 수 있을까요

dydsj0920 6년 전 0

hea1432 6년 전 1

dydsj0920 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말