[Python] 2248 이진수 찾기

[Gold III] 이진수 찾기 - 2248

[문제 링크](https://www.acmicpc.net/problem/2248)

---

💻 문제 정의

N자리 이진수가 주어지고, 해당 이진수에서 1의 개수가 L개 이하인 수들을 크기 순으로 나열하였을 때 I번째 이진수를 구하는 문제이다.

💡 접근 및 설계

DP테이블을 먼저 정의하였다. 이진수 나열 규칙을 살펴보면 다음과 같다.

자릿수 / 1의 개수 0 1 2 3 4 5 6 …

자릿수 / 1의 개수	0	1	2	3	4	5	6	…
0
1	1	1	0
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1
…

한 자릿수 일때, 1의 개수에 따라 만들어지는 수는 다음과 같다. $dp[1][0] = 1, dp[1][1] = 1$

즉, 0 과 1이다. 두 자릿수 일때도 한번 보자. $dp[2][0] = 1, dp[2][1] = 2, dp[2][2] = 1$이다. 즉, 00, 01, 10, 11이다. DP테이블의 값들은 자릿수x1의 개수 일때, 만들 수 있는 이진수의 개수가 된다.

해당 개수를 이용하여 우리는 주어진 I번째 수의 위치를 파악할 수 있게 된다.

문제 예제를 바탕으로, 5자리 이진수면서 1의 개수가 3개인 수들 중에서, 19번째 수를 구하기 위해선 어떻게 해야 할까?

우선 이진수의 제일 처음 올 비트를 생각해보자. 1 또는 0일 것이다. 이것을 결정하기 위해선 나머지 네 자릿수는 어떻게 결정될지 생각해보아야 할 것이다. 우선 만들 수 있는 4자리 수의 개수는 sum(dp[4])이 될 것이다. 그 중, 1의 개수가 3개 이하인 수들의 합은 sum(dp[4][0:4]) # 0, 1, 2, 3이 될 것이다. 개수는 15개 이므로 19번째 수는 1____가 될 것이다.

그 다음에 올 수는 다시 1 또는 0이 될 것이다. 이것을 결정하기 위해선 나머지 세 자릿수는 어떻게 결정될지 생각해보아야 할 것이고, 마찬가지 sum(dp[3][0:4])를 구하면 8이다. 앞서 1____라는 수를 먼저 얻었는데, 해당 수는 어쨋든 15번째 이후의 수이다. 그렇기에 ____ 부분의 숫자는 19-15인 4번째 수가 되어야 할 것이다. 4 < 8이므로 두번째 올 비트는 0이다. 따라서 10___이 될 것이다.

다음의 과정을 모든 자리수를 채울 때 까지 반복하면 최종적으로 I번째 이진수를 구할 수 있게 된다.

✏️ 알고리즘 풀이

dp = [[0] * (L+1) for _ in range(N+1)]

dp[0][0] = 1

# i자리수, 1의 개수가 j인 수의 개수를 구하는 dp
for i in range(1, N+1):
    dp[i][0] = 1
    for j in range(1, L+1):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

DP테이블은 다음과 같이 정의할 수 있다. N자리 수, 1의 개수가 L개 이하인 이진수들의 개수를 저장한다.

answer = ''
for i in range(N-1, -1, -1):
    if I > sum(dp[i][:L+1]): # i개 자릿수의 개수가 I번째의 수가 해당 범위안에 드는지
        answer += '1' # 아니라면 1을 앞에 붙인다.
        I -= sum(dp[i][:L+1])
        L -= 1

    else:
        answer += '0' # i개 자릿수들에 포함이 되기에 0을 붙인다.

앞서 설명한 1 또는 0을 채워나가는 과정이다. I번째 수를 구하기 위해 N-1자리수들의 개수를 빼면서 알맞는 위치를 찾아간다.

🗒️ 최종 제출 코드

# 2248 이진수 찾기

N, L, I = map(int, input().split())

dp = [[0] * (L+1) for _ in range(N+1)]

dp[0][0] = 1

# i자리수, 1의 개수가 j인 수의 개수를 구하는 dp
for i in range(1, N+1):
    dp[i][0] = 1
    for j in range(1, L+1):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

answer = ''
for i in range(N-1, -1, -1):
    if I > sum(dp[i][:L+1]): # i개 자릿수의 개수가 I번째의 수가 해당 범위안에 드는지
        answer += '1' # 아니라면 1을 앞에 붙인다.
        I -= sum(dp[i][:L+1])
        L -= 1

    else:
        answer += '0' # i개 자릿수들에 포함이 되기에 0을 붙인다.

print(answer)

---

💭 오늘의 회고

항상 어렵다고 말하는 DP이다. 언제쯤 쉬워질까? DP는 단순하게 생각하면 규칙찾고, 점화식 세우고, 나머지 조건 채우는 것이 다다. 정말 간단 명료한 문제이지만, 그만큼 어렵다는 것이 참 모순적이다.