DP를 이용해서 푸는 문제인데


많은 분들께서 


DP관련 배열을 잡으실때


[K][1<<(K+1)] 이런식으로 잡으시던데


1 << (K+1) 즉 왜 2의 K+1제곱으로 하시는지 궁금합니다.


너무 기초적인 질문일 수 있지만 이해가 잘되지 않아서 이렇게 질문드리게 되었습니다.

zlzmsrhak   1년 전

DP테이블의 정의가

DP[(현재 있는 도시 번호)][(지금까지 방문했던 도시들의 집합)]

으로 정의됩니다.

"지금까지 방문했던 도시들의 집합"은 0~2^K의 수 하나로 표현이 가능한데,

2진수로 표현했을 때 i번째 자릿수가 1인 경우 i번째 도시를 방문했다는 뜻입니다.

예를 들어, 5는 2진수로 표현하면 0101이고, 이 상태는 0번 도시와 2번 도시를 이미 방문했기 때문에 더 이상 방문할 수 없으며,

1, 3번 도시는 방문 가능하다는 것을 의미합니다.

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