[C++] 백준 - 16282 : Black Chain
16282번: Black Chain
문제 n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어야 하는데, 고리를 푸는데 힘이 들어 최소 개의 고리만 풀기를 원한다. 예를 들어 아래의 그림 A.1 처럼 7 개의 고리로 구성된 블랙 체인이 있다고 하자. 이 체인에서 3 번 고리 하나를 풀어 내면 그림 A.2 처럼 3 번 고리 1 개와 두 개의 체인
www.acmicpc.net
풀이 )
규칙성을 찾아내는 문제다.
풀어야 할 고리의 개수에 주목을 해보면
1번 끊었을 때 가능한 무게는 7g까지이다. 2 1 4
2번 끊었을 때는 1이 2개가 있으므로 3이 필요하고, 앞의 3개의 조합(1 1 3)으로 5까지 만들 수 있으므로 6이 필요하고
3 1 6 1 의 조합으로 11까지 만들 수 있으므로 마지막으로 12까지 총 23(3 1 6 1 12)까지 표현이 가능하다.
같은 방식으로 3번 끊었을 때는 총 4 1 8 1 16 1 32 의 조합으로 63까지 표현이 가능하다.
최대로 나타낼 수 있는 무게를 좀더 보기 쉽게 나타내면
- 1번 - 2 1 4 -> 7
- 2번 - 3 1 6 1 12 -> 23
- 3번 - 4 1 8 1 16 1 32 -> 63
- 4번 - 5 1 10 1 20 1 40 1 80 -> 159
- n번 - (n+1) 1 (n+1)*2 1 (n+1)*22 1 ... 1 (n+1)*2n 의 꼴임을 알 수 있다.
식을 정리하면 (n+1)(1+2+22+...+2n)+1*n = (n+1)(1+2+22+...+2n)+(n+1)-1 = (n+1)2n+1-1이다.
bound를 (n+1)2n+1라고 할 때 n값을 늘려주다가 입력값을 초과하는 경우 멈춰주면 된다.
다음 bound를 구할 때는 이전의 n으로 나눠준 후 다음번인 n+1을 곱하고 2를 한번 더 곱해서 구했다.
#include <cstdio>
using namespace std;
int main(void)
{
long long n, bound = 8, ans = 1;
scanf("%lld", &n);
while(n >= bound){
ans++;
bound = bound / ans * (ans+1) * 2;
}
printf("%lld\n", ans);
}