[BOJ 16282, Python 3] Black Chain

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

16282번: Black Chain

 

 

 

풀이

고리를 끊어내서 1g부터 ng까지 모든 무게를 생성해야 한다고 합니다.

이 문제는 보자마자 저울이라는 그리디 문제가 생각났습니다.

블랙 체인 문제는 직접 고리를 끊어내서 1g부터 ng까지 모든 무게를 표현할 수 있어야하는 것이고, 위 그리디 문제는 주어진 추들이 있을 때 이 추들을 사용해서 표현하지 못하는 최소 그램수를 출력하는 문제라 두 문제의 아이디어는 똑같습니다.

 

고리를 사용하여 1g부터 ng까지 모든 무게를 표현할 수 있으려면 무게순으로 오름차순을 한 뒤 하나씩 더해가면서 (현재까지 더한 고리의 총 무게의 합) + 1 >= (다음 고리의 무게)를 만족하면 됩니다.

예를 들어서 지금까지 나온 고리의 무게가 1, 2, 3이라면 다음 고리의 무게는 7까지 나올 수도 있다는 것이죠

 

이제 아이디어는 알아냈으니 고리를 몇 번 끊어낼 때마다 최대 몇 그램까지 표현할 수 있는지 확인해봅시다.

 

일단 1번 끊을 때는 1g이 존재합니다. 이후엔 2g이하의 체인이 필요하니 우리는 최댓값을 구하므로 2g을 선택합니다. 이러면 총 3g이 되는데, 고리를 최대 4g까지 만들 수 있으니 4g을 선택하여 7g까지는 고리를 1개만 끊어서 만들어낼 수 있습니다.

 

2번 끊을 때는 1g이 2개 존재합니다. 이후 최댓값인 3g을 선택하고, 합이 5g이니까 최댓값인 6g을 선택하고, 합이 11g이니까 최댓값인 12g을 선택하면 총 (3 + 1 + 6 + 1 + 12) = 23g까지 표현이 가능합니다.

 

마찬가지로 3번 끊을 때는 (4 + 1 + 8 + 1 + 16 + 1 + 32) = 63g, (5 + 1 + 10 + 1+ 20 + 1 + 40 + 1+ 80) = 159g .... 이렇게 답을 찾아낼 수 있습니다.

 

위 식들을 보면 한가지 규칙성이 보입니다. 고리를 x번 끊었으면 첫번째 값은 x+1이 되어있고, 홀수번째 값은 이전 홀수번째 값의 두 배씩 증가합니다.

식 표현의 편의를 위해서 고리를 x-1번 끊으면 첫 번째 값은 x라고 해봅시다.

그러면 식은 $a_n = (n + 2n + 4n + .... + 2^{n-1} \times  n) + (n-1)$ 꼴로 나타낼 수 있습니다.

$(n + 2n + 4n + ... + 2^{n-1} \times  n) = n \times  (1 + 2 + 4 + .... + 2^{n-1})$ 형태로 정리해줄 수 있고

이걸 등비수열의 합으로 정리하면 $n \times  (1 + 2 + 4 + .... + 2^{n-1}) = n \times  (2^n - 1)$ 형태로 표현할 수 있습니다.

그러면  $a_n = (n + 2n + 4n + .... + 2^{n-1} \times  n) + (n-1) = n \times  (2^n - 1) + (n - 1) = n \times  2^n - 1$이 됩니다.

 

log2(10**18)은 대략 59.xx이니까 배열에 저장해두고 n을 입력 받았을 때 n <= arr[i]을 만족하면 출력하면 됩니다.

 

코드

아이디어를 설명하는데 오래 걸려서 그렇지 코드는 간단합니다.

arr = [n*(2**n-1) + (n-1) for n in range(2, 60)]
val = [i for i in range(1, 59)]
n = int(input())
for i in range(len(arr)):
    if n <= arr[i]:
        print(val[i])
        break