[백준] 20941. 성싶당

https://www.acmicpc.net/problem/20941

문제요약

• n개의 비트를 모두 나열하는데 ${b_0, b_1, ...}$
• ${b_i, b_{i+1}}$ 의 서로 같은 비트의 개수를 x 라고 할 때
• x의 합을 최소로 하는 나열을 구하기

접근법

• 반전된 비트는 모두가 서로 다른 비트일 것임 : 같은 비트의 개수가 0
• 일단 서로 반전된 비트끼리 인접하면 좋을 것 같음
• 반전하지 않고 다른 비트로 이동하려면 최소 1개는 같아야할 것임
  • a -> (~a에서 0번째 비트만 같음), (~a에서 1번째 비트만 같음), .... 최대 n개의 경우의 수를 찾을 수 있음
• n개의 경우 중에서 기존에 방문하지 않은 비트로 이동하고 계속 반복한다면?
  • a 출력, ~a 출력, ~a에 대해서 다음에 이동할 것들을 찾음(최대 20개)
    • ~a의 반전인 a에서, ~a와 0번째 비트만 같은것, 1번째 비트만 같은 것, ... 중 기존에 방문하지 않은 것 선택
  • 일단 출력한 비트는 방문 처리
  • 중복을 피해서 이동하면 모든 비트를 이동할 수 있을까?
• 일단 구현하고 테스트해봄 => n <= 20에서 모든 비트를 이동함(대략 파악함)

추가

• 왜 되는지는 잘 모르겠으나 될 것 같다는 생각은 들었음
• graycode 문제라고 함