백준 21854번: Monsters

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

21854번: Monsters

---

오랜만에 보는 쉬운 문제입니다.

 

예제에서 다음 세 가지 특징을 알 수 있습니다.

 

$\left ( 1 \right )$ 아무것도 안 쓰는 경우에 $0$ 을 얻는다.

$\left ( 2 \right )$ $1$ 번 손가락부터 $\left ( k_{i}-1 \right )$ 번 손가락까지 모두 썼을 때 $\left ( 2^{k_{i}}-1 \right )$ 을 얻는다.

$\left ( 3 \right )$ 그 사이의 숫자는 모두 반드시 얻을 수 있다.

 

그래서 얻을 수 있는 숫자는 $0$ 부터 $2^{k_{i}}-1$ 까지의 모든 정수이고, 이 갯수는 $2^{k_{i}}$ 입니다.

 

결론적으로, 다음을 계산해주면 끝입니다.

 

$\sum_{i=1}^{N} 2^{k_{i}}$ $mod\left ( 10^{9}+7 \right )$

 

최종적인 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

int main() {
	
	int N, k;
	long long Result = 0;
	scanf("%d", &N);
	
	while(N--) {
		scanf("%d", &k);
		long long temp = 1, base = 2;
		while(k > 0) {
			if (k & 1) {
				temp = base * temp % mod;
			}
			base = base * base % mod;
			k >>= 1;
		}
		Result = (Result + temp) % mod;
	}
	printf("%lld", Result);
	return 0;
}

(C11, 1112KB, 52ms, 제출번호 31080922)

---

$\left ( 2 \right )$ 번 성질에 관한 증명이 필요할까요?

 

$k_{i}=2$ 일 때 경우의 수가 다음과 같습니다.

 

$0$ : 어떤 손가락도 들지 않는 경우

$1$ : 0번 손가락만 드는 경우

$2$ : 1번 손가락만 드는 경우

$3$ : 0번, 1번 손가락을 드는 경우

 

$k_{i}=\alpha$ 일 때 다음이 성립한다고 합시다. ( 단, $\alpha \geq 2$ )

 

$0\sim \alpha -1$ 번 까지의 손가락을 통해 만들 수 있는 수의 집합이 다음과 같다.

$\left \{ 0,1,2,\cdots,2^{\alpha}-1 \right \}$

 

그러면 $k_{j}=\alpha +1$ 에 대해

 

$0\sim \alpha$ 번 까지의 손가락을 통해 만드는 수를 두 가지로 분류할 수 있습니다.

 

$\left ( 1 \right )$ $\alpha$ 번 손가락을 쓰지 않고 만드는 수

$\left ( 2 \right )$ $\alpha$ 번 손가락을 반드시 써서 만드는 수

 

이때 우리는 $\left ( 1 \right )$ 의 집합이 $\left \{ 0,1,2,\cdots,2^{\alpha}-1 \right \}$ 임을 알 수 있습니다.

그리고 자연스럽게 $\left ( 2 \right )$ 의 집합이 $\left \{ 2^{\alpha},2^{\alpha}+1,2^{\alpha}+2,\cdots,2^{\alpha+1}-1 \right \}$ 임을 알 수 있습니다.

 

따라서 둘을 합집합하면 $\left \{ 0,1,2,\cdots,2^{\alpha+1}-1 \right \}$ 이 나오며,

 

수학적 귀납법에 의해 자연수 $k_{i}$ 가 주어지면 그 답이 $2^{k_{i}}$ 가 됨을 알 수 있습니다.