문제 보기
bit DP 유형의 기본 문제이다.
오늘 bit DP를 접했는데 매우 인상깊어서 남겨본다.
bit DP가 뭔가요?
일반적인 dp는 인자로서 수 몇 개 정도가 들어간다.
그런데, 집합에 대한 일정한 output도 대응시킬 수가 있는 것이다.
이게 왜 필요하냐 하면,
은 미친듯이 빠르게 커지는 시간 복잡도인데 반해, 은 훨씬 적은 시간 복잡도를 가지기 때문이다.
체감을 시켜드릴까요?
ABCD... 방문이 있고,
BCAD... 방문이 있고,
ACBD... 방문이 있고,...
더럽게 많습니다.
따라서 D로 끝나는 경우들만 묶어다가 최소만을 취급합시다. 어차피 그 많은 경우 중에서 사용할 경우는 최소인 경우 뿐일테니까요.
그러면 계승단위가 지수단위로 바뀌는 기적을 경험하게 됩니다!!
bitmask를 써야하는 이유라도 있어?
근데 그냥 집합을 인자로 사용하게 되면 map을 써야 하는데, 일단 너무 비쌉니다.
그래서 제끼고 정수와 집합을 대응시키는 미친 발상을 하게 됩니다.
바로 비트마스크를 이용해서 말이죠!
어차피 집합의 원소가 많아지면 애초에 다 돌아갈 수가 없어서, 원소의 개수가 거의 20 이내로 들어옵니다.
그러면 int로도 충분히 커버할 수 있게 됩니다. (개인적으로는 unsigned보다 그냥 부호있는 것을 권합니다. 원소가 모두 on인 상태는 -1, 모두 off인 상태는 0으로 손쉽게 표현할 수 있기 때문이죠.)
이 문제 풀면서 내가 틀렸던 점!!
믿는 INF에 발등 찍힌다
INF를 실수로 INT_MAX로 잡았다가 덧셈에서 오버플로우를 겪었습니다.
이거 찾아주신 djm님 사랑해요!!
아니 못 가면 0이라고;;
w[i][j]=0인 경우는 갈 수 있는 경로가 없는 것이라고 문제에 명시되어 있음에도
저를 포함한 다수의 사람들이 여기서 헤맸을 것입니다.
그 외에는 딱히 문제 없었네요!
질문은 언제든 댓으로 남겨주세염..!
