[C++] BAEKJOON 16282 Black Chain

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

16282번: Black Chain

체인의 길이에 대해서 풀어야 할 고리의 최소 개수를 구하다보니 규칙을 찾을 수 있었습니다.

• 한 개의 고리를 끊을 경우

  우선 고리를 끊으면 길이 1의 고리가 만들어집니다. 그럼 고리를 한 번 끊을 경우에는 1이 하나 존재하므로 2를 만들기 위해 길이가 2인 고리도 만들어 줘야합니다. 이제는 1인 고리와 2인 고리로 3을 만들 수 있으므로 다음 필요한 고리의 길이는 4 입니다. 따라서 고리는 다음과 같이 끊을 수 있습니다.

  OO O OOOO

  가장 끝의 고리가 5이상이 되는 순간 길이 4에 해당하는 고리를 만들 수가 없어서 불가능하게 됩니다. 즉 한 개의 고리를 끊는 경우에는 길이 7까지 커버가능합니다.

• 두 개의 고리를 끊는 경우

  마찬가지로 고리를 끊으면 길이 1의 고리가 만들어지는데 두 번 끊으므로 길이 1의 고리가 2개 만들어집니다. 즉 1,2 가능해지므로 다음 필요한 길이는 3 입니다.

  OOO O X O Y

  현재까지 고리는 다음과 같습니다. 마저 X 와 Y 도 찾아보도록 하겠습니다. 3개 짜리 고리 1개와 1개짜리 고리 2개를 이용하면 5까지 만들 수 있으므로 X 는 6이 되어야 합니다.

  OOO O OOOOOO O Y

  이번에는 길이 6짜리 1개, 3짜리 1개, 1짜리 2개를 이용해서 최대 11까지 만들 수 있고 Y는 길이 12의 고리가 됩니다. 또한 모든 고리를 이용해서 23까지 커버가능합니다.

 

위에 두 케이스를 정리해보면

n = 1) OO O OOOO

n = 2) OOO O OOOOOO O OOOOOOOOOOOO

다음과 같고 숫자로 표현하면 규칙이 더 잘 보입니다.

n = 1) 2 1 4

n= 2 ) 3 1 6 1 12

...

n = k) 1X(k+1) 1 2X(k+1) 1 2^2X(k+1) … 2^kX(k+1)

따라서 등비수열의 합 공식을 사용하여 다음 식을 정리하면 다음과 같습니다.

n번 짜르는 경우, 최대로 표현할 수 있는 길이는 (n+1) X (2^(n+1)-1) + n

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    long long n;
    cin >> n;
    
    for (long long i=1;i<=n;i++){
        long long limit = (i+1LL)*((1LL<<(i+1))-1) + i;
        if (n<=limit){
            cout << i;
            break;
        }
    }
    return 0;
}