220924 문제 풀이 기록

P4 | 9569 - No Change

풀이 시간: 1시간

시도 횟수: 3회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

대놓고 bitfield DP + 약간의 이분 탐색

여담: 처음에는 DP 설계 자체를 엉망으로 해서 -1, 이분 탐색 안해서 -1 후 해결.

for (int i=0; i< (1 << k); i++) 에서 i ^ s 하는것만으로도 해결 가능했는데, 비트마스킹에 익숙하지 않아서 그 사실을 모르고 그냥 builtin__popcount로 1의 개수에 해당하는 2차원 벡터를 차례대로 순회하도록 하여 해결했다.

문제 풀이 자체는 재밌었지만, 딱히 풀이를 쓸 건덕지가 없어서 풀이 쓸 의향은 下로 준다.