문제 설명
숫자 n이 주어졌을 때, 1부터 n까지 각 숫자의 이진 표현을 순서대로 하나씩 이어 붙여 만들어진 이진 문자열의 십진수 값을 구하는 것이 목표입니다. 만약 결과값이 너무 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
예를 들어 입력이 n = 4라면 출력은 220이 됩니다. 1부터 4까지의 이진 표현을 차례대로 이어 붙이면 "1" + "10" + "11" + "100" = 110111000이 되고, 이 값은 바로 십진수 220의 이진 표현이기 때문입니다.
해결 접근 방법
이 문제는 실제로 문자열을 이어 붙이지 않고도 비트 시프트 연산을 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 새로운 숫자 i를 뒤에 추가하려면, 기존 결과값을 i의 비트 길이(bit length)만큼 왼쪽 시프트하여 빈자리를 만든 후 i를 더해주면 됩니다.
해결 단계는 다음과 같습니다.
- ans := 1 로 초기화합니다.
- m := 10^9 + 7 을 정의합니다.
- i를 2부터 n까지 반복합니다.
- ans를 i의 비트 길이만큼 왼쪽 시프트합니다.
- ans := (ans + i) mod m 으로 갱신합니다.
- ans를 반환합니다.
비트 길이만큼 시프트하는 것은 해당 숫자의 이진 표현을 뒤에 덧붙이는 것과 동일한 효과를 내므로, 문자열 변환 없이 O(log n) 수준의 연산으로 처리할 수 있다는 장점이 있습니다.
구현 예시
다음 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.
def solve(n): ans = 1 m = (10**9+7) for i in range(2,n+1): ans = ans<<i.bit_length() ans = (ans+i) % m return ans n = 4 print(solve(n))
입력
4
출력
220