kokoxg2   6년 전

외판원 순회 문제를 접하고 비트 마스킹이란 걸 알게되었습니다.

DP를 선언할 때 DP[16][1<<16]으로 표현을해서 각 도시를 방문했는지 안했는지를 표현하게 되는데

비트마스킹을 사용하지않으면 16차원의 bool 배열을 사용해야한다는데 이 부분이 잘 이해가 가지않습니다.

왜 비트마스킹을 사용하지 않으면 N 차원 (N은 도시의 수) 배열을 사용해서 방문 여부를 표시해야하나요 ?

생각을 해봐도 잘 떠오르질 않습니다.

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