boj 2248 : 이진수 찾기

boj 2248 : 이진수 찾기

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

처음에 단순 완전 순열 탐색 DFS로 찾으니 역시나 시간초과. ㅜㅜ

다른방법을찾았다.

1. 맨 앞에 1을 두고 나머지 자리수를 0으로 채우면 최소 몇번째 숫자일까?

2. 맨 앞에 0을 두고 나머지 자리수를 0으로 채우면 최소 몇번째 숫자일까?

위의 1,2 두가지의 값으로 찾았다.

1. N, K : 각각 남은 자릿수, 남은 1의 갯수

2. a[N][K] : N의 자리에 1을 채우고 나머지를 0으로 채웠을 때 몇번째 값인지?

3. a[N][K] = sum{ (N-1,0) ~ (N-1,K) } : (i,j) 는 iCj (i combination j)

a[N][K]가 주어진 I보다 작거나 같으면 N의 자리에 1을 채우고, 그렇지 않으면 0을 채우는 방법으로 문제를 해결할 수 있었다.