비트마스킹 사용에 관한 질문입니다.

4주차 이론을 듣고 4-a 를 풀어봤습니다.

http://boj.kr/1505ce542738451d97357d5977350e46

문제를 딱 보자마자 그냥 완전탐색으로 풀어야겠다고 생각하고

비트마스킹 생각을 하지않고 그냥 문제를 풀게 됐고 그 후

강의를 보니 비트마스킹을 사용해서 풀이하신 걸 보고

어떻게 이 문제를 보고 비트마스킹을 사용해야겠다고 생각하신건지 비트마스킹의 장점이 무엇인지 궁금해서 질문남깁니다.

1.경우의 수를 탐색하는 문제에서 사용하는 것 같은데 나중에는 무조건 비트마스킹을 사용해야만 하는 문제도 있나요? 아니면 이 문제처럼 그냥 완전탐색으로 풀어도 대부분 풀리는 건지 궁금합니다!

2. 비트마스킹의 장점은 속도 인가요? 시간 초과가 타이트할 때 사용하는 건지 아니면 다른 장점이 있는 건지 궁금합니다.

이론강의를 듣고 나서도 잘 이해가 안가서 질문드립니다!

안녕하세요 구인님 ㅎㅎ

>> 모든 경우의 수를 탐색할 때 비트마스킹을 쓰면 좀 더 간단해집니다. (다만 완탐으로 풀어도 상관은 없습니다.)

nC1, nC2, nC3 .. 이런식으로 모든 경우의 수를 탐색해야 할 때는 비트마스킹 쓰는게 좋습니다. (코드가 더 간단해짐)

하지만 n이 30이하 또는 31 이하 일 때만 사용가능하다는 제약조건이 있긴 합니다.

2. 비트마스킹의 장점은 속도 인가요? 시간 초과가 타이트할 때 사용하는 건지 아니면 다른 장점이 있는 건지 궁금합니다.

>> 네 속도가 빠릅니다. 기본적으로 재귀함수보다는 비트마스킹 - 반복문 돌려서 하는게 더 빠릅니다.

코드리뷰.

	for (int i = now; i < n; i++)
	{
		choice.push_back(i);
		food[0] += foods[i][0];
		food[1] += foods[i][1];
		food[2] += foods[i][2];
		food[3] += foods[i][3];
		select(i + 1, price + foods[i][4]);
		choice.pop_back();
		food[0] -= foods[i][0];
		food[1] -= foods[i][1];
		food[2] -= foods[i][2];
		food[3] -= foods[i][3];

	}

근데 정말 대단하시네요 ㅎㅎ

다이어트를 이렇게 푸신건 아마 구인님이 처음이신 것 같아요. i + 1해서 하신 것도 좋고... 코드가 깔끔하고 너무 좋습니다.

아름다움 그 잡채네요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변