[Algorithm] Brute-Force Attack (Algospot – BRUTEFORCE)

by

문제 출처

  • https://algospot.com/judge/problem/read/BRUTEFORCE

문제 난이도 

  • 하 – (중) – 상 – 최상 – 풀지 못함

문제 설명 (항상 대략적인 설명만 작성합니다.  문제는 위 출처에서 확인하세요)

  • 총 암호 조합의 수를 계산하는 문제이다. Input으로 최소 암호 자릿수, 최대 암호 자릿수가 주어진다. 이와 더불어 각 암호 자리당 들어갈 수 있는 input (Char)의 개수가 주어진다. 예를 들어 최소/최대 4자리 암호 자릿수와 각 자리당 숫자 0~9까지 10개의 input이 가능하면 총 가능한 암호 조합의 수는 0000부터 9999까지 10000개가 된다. 가능한 암호 조합의 수가 너무 많은 수도 있기 때문에 1000000007로 나눈 나머지 값을 출력하는 문제이다.

후기

  • 개인적으로 문제가 몹시 어렵다는 생각이 들지는 않았다. 문제를 읽는 순간 분할정복으로 문제를 풀어야 한다는 생각은 했지만, 혼자서 식을 성립하지 못하여서 인터넷의 힘을 빌렸다. 왜 답을 보고 나면 내가 다시 계산해도 손쉽게 계산이 되는 것인지 잘 모르겠다 ㅠㅠ. 관련 식은 아래 출처에 더 상세히 정리되어 있다.
  • 주어진 자릿수의 총 암호 개수를 계산하기 위해서는 최대 암호 자릿수의 개수를 모두 구한 후 최소 암호 자릿수의 개수를 빼주면 답을 쉽게 찾을 수 있다. 본 문제에서 해결해야 하는 부분은 주어진 암호 자릿수의 총 암호 개수를 구하는 것이 제일 중요하다.
  •  예를 들어 암호는 9자리이며 각 자리에 3개의 input을 사용할 수 있다면 총 가능한 암호의 수는 아래의 식과 같다. (3^4는 3을 4번  곱한 것을 의미한다)
    • calP(3, 9) = 3^1 + 3^2 + 3^3 + 3^4 + 3^5 + 3^6 + 3^7 + 3^8 + 3^9
  • 위 식을 다시 정리하면 아래와 같이 된다.
    • calP(3, 9) = 3^1 + 3^2 + 3^3 + 3^4 + 3^4 * (3^1 + 3^2 + 3^3 + 3^4) + 3^9
  • 3^1 + 3^2 + 3^3 + 3^4을 구하는 식을 calP(3, 4)으로 찾을 수 있다. 위 와 같이 식을 정리하면 calP(3, 4)계산 한 번으로 3^8까지 연산할 수 있다. 다시 식을 정리하면 아래과 같다.
    •  calP(3, 4) * (1 + 3^4) + 3^9
  • 이렇게 위에 보이는 식을 이용하면 분할정복으로 본 문제를 해결 할 수 있다.

코드

#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996) 

#define MOD 1000000007 

//MK: 분할 기법을 사용하여 power 을 계산하는 부분
long long power(long long base, long long top) {
	if (top == 1) {
		return base;
	}
	long long ret = power(base, top / 2) % MOD;
	ret *= ret;
	ret %= MOD;
	if (top % 2 == 1) {
		ret *= base;
	}
	return (ret % MOD);
}

//MK: 분할 기법을 사용하여 calP를 계산하는 부분
long long calP(long long base, long long top) {
	if (top == 0) {
		return 0;
	}
	if (top == 1) {
		return base;
	}
	long long ret = calP(base, top / 2) % MOD;
	ret = (ret * (1 + power(base, top / 2))) % MOD;
	if (top % 2 == 1) {
		ret += power(base, top) % MOD;
	}
	return (ret % MOD);
}


int main(void)
{
	int testCase;
	//MK: input.txt로 부터 input 데이터를 읽어오기 위한 부분. 문제를 체줄할때는 지워야함.
	freopen("input.txt", "r", stdin); 
	setbuf(stdout, NULL);
	scanf("%d", &testCase);
	for (int i = 1; i <= testCase; i++)
	{
		long long begin, end, base;
		scanf("%lld %lld %lld", &begin, &end, &base);
		//MK: MOD를 더하는 이유는 앞의 수가 더 작을 수도 있기 때문에 더해서 다시 나머지 값을 계산해야함.
		long long answer = (calP(base, end) - calP(base, begin - 1 ) + MOD) % MOD;
		printf("%lld\n", answer);
	}
	return 0;
}

출처

  • http://orangenius.tistory.com/entry/Dev-AOJBrute-Force-Attack

Leave a Comment