Bit DP (1) 썸네일형 리스트형 79. Bit DP 비트마스크를 이용한 동적 계획법(Bit DP)에 대해 다룬다. 일반적으로 이 유형의 문제들은 제한이 $20$ 이하로 작은 변수가 주어지는 경우가 많으며, 이 변수에 대한 각각의 상태를 비트마스크로 나타냄으로써 문제를 해결할 수 있다. 동적 계획법이 비트마스크를 이용할 경우 이때의 DP 테이블을 비트필드(Bitfield)라고도 한다. [연습문제] BOJ 1562. 계단 수 (Gold I)더보기현재까지 사용된 숫자의 조합과 수의 길이를 기준으로 비트필드를 채운다. 사용된 숫자의 조합은 $2^{10}$개 이하로 나오며 (아무 숫자도 사용하지 않는 경우나 사용한 숫자가 연속되지 않는 경우가 모두 제외된다. 다만 실제로 문제를 풀 때는 별로 신경쓰지 않아도 된다) $\Theta(2^{10} \cdot N)$ 시간.. 이전 1 다음
