BOJ 20941 - 성싶당
비슷한 문제를 이전에 풀어본적이 있어서 그냥 떠올리는대로 풀 수 있었다.
뭐 그레이코드라는 것과 관련된 문제라고 하는데 굳이 필요없다.
현재 어떤 비트 $b$일 때, 가장 그리디하게 가는 방법은 $(2^N-1) \oplus b$ 로 이동하는 것이다.
그럼 하나도 겹치지 않기 때문이다.
그렇지 않다면 항상 $(2^N-1) \oplus b$ 와 비트가 하나만 다른 것 중 아직 쓰이지 않은 것으로 가기만 하면 된다.
어쨌든 그냥 그레이 코드라는 것이 존재하며 항상 그리디하게 비트가 하나만 다른쪽으로 이동할 수 있는 방법이 있다는 것만 캐치해도 될 것 같다.
Comments