글 읽기 - 비트마스크-완전탐색이 왜 틀릴까요....?

wjddydgns99 4년 전 0

게시판 거의 다 확인하면서, 반례를 찾아보았는데 발견하지 못했습니다.

계산해보니 자료형에 걸리진 않는데 혹시나? 해서 long long 으로 바꾼 코드입니다.

#include<iostream>

using namespace std;

long long a[101];
int main()
{
	int n, m;
	cin >> n >> m;
	long long max = 0;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < (1 << n); i++)
	{
		int count = 0;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j)) count++;
		}
		if (count != 3) continue;
		long long sum = 0;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j)) sum += a[j];
		}
		if (sum <= m && max <= sum)
		{
			max = sum;
		}
	}
	cout << max;
	return 0;
}

pichulia 4년 전 1

비트마스크를 사용한 것이 잘못됐기 때문입니다.

1<<n 을 사용하셨는데.. 의미상으론 2^100 = 약 1.26765 * 10^30 가지의 경우를 모두 확인해본다는 의미이기 때문에 초당 10^10번의 연산을 할수있다고 해도 약 10^15년이 걸리기 때문에 느립니다.

뿐만아니라 1<<100을 사용하면 32bit를 넘어가버리기 때문에 1<<n 결과값은 그냥 0이 되버립니다.

wjddydgns99 4년 전 0

그렇네요... 시간복잡도를 고려를 안했네요... 감사합니다.

sait2000 4년 전 0

여담이지만 1<<100은 UB입니다

wjddydgns99 4년 전 0

UB 가 Undefined Behavior 말씀하시는 건가요?

왜 1<< 100 이 UB인가요?

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

문제

문제

출처

ICPC

비트마스크-완전탐색이 왜 틀릴까요....?

wjddydgns99 4년 전 0

pichulia 4년 전 1

wjddydgns99 4년 전 0

sait2000 4년 전 0

wjddydgns99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말