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

By | 2018-07-10

문제 출처

  • 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
  • 이렇게 위에 보이는 식을 이용하면 분할정복으로 본 문제를 해결 할 수 있다.

코드

출처

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

Leave a Reply

Your email address will not be published. Required fields are marked *