BOJ 2248 이진수 찾기

참조 : kks227님 블로그

이 문제는 처음에는 전혀 감도 못잡다가... 운 좋게도 kks227님의 친절하고 자세한 설명이 나온 블로그를 찾았다! 보니까 이 문제뿐 아니라 dp에 대한 설명, 문제 추천, 그리고 다른 여러가지의 대회 알고리즘에 대한 설명과 문제 풀이까지 엄청난 자료들을 직접 정리 해놓으신 것 같다... 나중에 꼭 다 읽어보고 공부해야 겠다.

이 문제는, N자리의 이진수들 중에서 L개 이하의 비트만 1로 이루어진 이진수들을 크기순으로 나열했을 때, I번째 이진수를 구하는 것인데, 내가 여태 푼 dp는 최대값, 최소값, 경우의 수를 구하시오가 대부분이었는데... 그러나 이 문제는 내가 풀어본 것은 아니더라도, 처음 보는 방식은 아니었다. 최대값, 최소값, 경우의 수를 구할 때 다시 역추적하는 것을 해본 적이 있는데, 이것 또한 그런 맥락으로 볼 수 있겠다.

바로... N자리의 이진수들 중에서 L개 이하의 비트만 1로 이루어진 이진수의 개수를 먼저 생각해보는 것이다. 이것은 dp로 충분히 풀 수 있을 것이다.(사실 난 이것도 처음에 멈칫했다...) D[N][L]을 N자리의 이진수들 중에서 L개 이하의 비트만 1로 이루어진 이진수의 개수라고 정의하면, D[N][L]=D[N-1][L-1]+D[N-1][L] (N번째 자리에서 1을 사용하는 경우와 사용하지 않는 경우의 합)으로 나타낼 수 있다.

근데 이것을 구해서 뭘 어떻게 하려는건가? 잘 보면, 크기순(오름차순)으로 나열할 경우, 왼쪽에서 첫번째 자리에 0이 오는 수는 뒤에 아무리 1이 많이 나와도 첫번째 자리에 1이 오는 수보다는 앞에 위치한다.
D[N][L]=D[N-1][L-1]+D[N-1][L] 다시 이 식을 보면 첫 자리에 1을 쓰냐 0을 쓰냐로 나뉘고, 첫 자리가 1인 경우의 수와 첫 자리가 0인 경우의 수를 D[N-1][L-1], D[N-1][L]배열이 갖고 있다. 그리고 I번째수와 그 경우의 수를 비교하면서 재귀적으로 더 들어가보면, 계속 1을 쓰냐 안쓰냐로 나뉘고, I번째 수와 비교하면서 그 때 그 때 출력을 해주거나 저장을 해주면, 결국 I번째 수가 어떤 수인지 나오게 된다.

마지막으로 하나 더, 내가 이 문제를 엄청 많이 틀렸는데, 이유는 다름 아닌 변수 자료형에 있었다. 31자리의 이진수이고 이진수가 0부터 시작한다고 하면 I는 최대 2의 31제곱이 입력으로 들어올 수 있는데, int형 범위는 2의 31제곱-1까지... 그래서 long long을 쓰든지, I가 2의 31제곱인 경우만 예외처리를 해주든지 해야한다!