DP테이블의 정의가
DP[(현재 있는 도시 번호)][(지금까지 방문했던 도시들의 집합)]
으로 정의됩니다.
"지금까지 방문했던 도시들의 집합"은 0~2^K의 수 하나로 표현이 가능한데,
2진수로 표현했을 때 i번째 자릿수가 1인 경우 i번째 도시를 방문했다는 뜻입니다.
예를 들어, 5는 2진수로 표현하면 0101이고, 이 상태는 0번 도시와 2번 도시를 이미 방문했기 때문에 더 이상 방문할 수 없으며,
1, 3번 도시는 방문 가능하다는 것을 의미합니다.
2blikecaesar 7년 전
DP를 이용해서 푸는 문제인데
많은 분들께서
DP관련 배열을 잡으실때
[K][1<<(K+1)] 이런식으로 잡으시던데
1 << (K+1) 즉 왜 2의 K+1제곱으로 하시는지 궁금합니다.
너무 기초적인 질문일 수 있지만 이해가 잘되지 않아서 이렇게 질문드리게 되었습니다.