[Algorithm] 백준 16282 - Black Chain 풀이 (feat. pow 문제점)

풀이

일단 시간제한이 0.1초이기 때문에 규칙을 찾는 문제라는것은 이해하였다. 규칙을 찾기 위해서는 직접 써가면서 푸는것이 나에겐 가장 효과적이다. 

 

 

n = 1일 때, (즉 고리를 한 개 끊을 경우)

• X 1 Y 라고 생각할 수 있다. (X와 Y는 고리의 개수)
• 이제 여기서 생각을 해보자 1은 만들 수 있고(잘라진 chain으로 1g 만들기) 2부터 만들 수 없다. 따라서 X = 2이다.
• X가 2이면 1, 2, 3(1 + 2)g 까지 만들 수 있다. 이제 만들지 못하는 것은 4g 부터이다. 따라서 Y= 4g.
• n = 1일때 7g까지 만들 수 있다. 1, 2, 3(2 + 1), 4, 5(4 + 1), 6(4 + 2), 7(2 + 1 +4)

n = 2일 때, (즉 고리를 두 개 끊을 경우)

• A 1 B 1 C 라고 생각할 수 있다. (A, B, C는 고리의 개수)
• 이제 여기서 생각을 해보자. 1과 2는 만들 수 있고(잘라진 chain으로 1과 2(1 + 1)g 만들기) 3부터 만들 수 없다. 따라서 A = 3이다.
• A가 3이면 1, 2, 3(1 + 2), 4, 5g 까지 만들 수 있다. 이제 만들지 못하는 것은 6g 부터이다. 따라서 B = 6g.
• B가 6g이면 1, 2, 3(1 + 2), 4, 5,....11g 까지 만들 수 있다. 이제 만들지 못하는 것은 12g 부터이다. 따라서 C = 12g.
• n = 2일 때, 23g까지 만들 수 있다. 

이런식으로 만들면 규칙을 발견할 수 있다. 

 

n = 1일 때, 2 + 1 + 4

n= 2 일 때, 3 + 1 + 6 + 1 + 12

...

n = k일 때,  1*(k+1) + 1 + 2*(k+1) + 1 + … (2^k)*(k+1)

등비수열의 합 공식을 사용하여 위의 규칙을 정리하면 (n+1) * ( {2^(n+1)} - 1 ) + n 이런식이 나오게 된다.

---

코드

형변환 하지않고 pow를 사용해서 풀었더니 오답이 나왔다. 그 이유는 pow는 연산 결과가 double형으로 반환되기 때문이다. floating point 방식으로 연산결과를 return 하기 때문에 int형으로 형변환 해주어야한다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    
    long long int n;
    scanf("%lld", &n);
    for(long long int i = 1; i < n; i++)
    {
        long long int a = ( (long long int)pow(2, i+1 ) - 1 ) * ( i + 1 ) + i;
        if( n <= a )
        {
            printf("%lld\n", i);
            break;
        }
    }   
}