[BOJ 17205] 진우의 비밀번호 - JAVA, Gold5

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

17205번: 진우의 비밀번호

사용한 알고리즘 : 수학, 중복순열

 

풀이전략

3
ca

위와 같은 입력이 주어졌다고 생각해보자.

 

그러면 비밀번호 시도 순서는 아래와 같을 것이다.

a

aa

aaa ~ aaz  - 26개

ab

aba ~ abz  - 26개

      ...

az

aza ~ azz  - 26개

 

b

ba

baa ~ baz ~26개

bb 

bba ~ bbz  - 26개

      ...

bz

bza ~ bzz  - 26개

 

c

ca

 

-----------------------------------------------------

즉,

a ,b - 2개

aa~az, ba~bz - 26^1개

aaa~azz, baa~bzz - 26^2개

c, ca - 2개

번 수행되는 것을 알 수 있다.

 

여기서 수학적 반복과정을 찾을 수 있는데

입력으로 주어진 ca의 첫번째 문자 c는 보다 작은 문자로 a,b를 가진다.

 

비밀번호를 최대 3자리 수 까지 가질 수 있으므로

a,b 로 시작하며 가질 수 있는 각각의 경우의 수는

26^2 + 26^1 +1 개이다.

 

왜냐하면 a만 보았을 경우 아래와 같은데,

aaa ~ aaz : 26개

aba ~ abz : 26개

       ...

aza ~ azz : 26개  

==================== >> 26*26 = 26^2

aa ~ az : 26개

==================== >> 26*1 = 26^1

a

==================== >> 1

따라서 결과 a로 시작하여 만들 수 있는 비밀번호의 경우의 수는 26^2 + 26^1 + 1개 이다.

 

그런데 c보다 작은 문자로 a,b 2개가 있으므로

(26^2 + 26^1 + 1) * 2개를 가진다.

 

위의 경우의 수를 거치고 나서 나오는 문자열은 bzz이다.

 

따라서 우리가 구하는 최종 문자열은 ca이므로 2를 더 더한 값이 우리가 구하는 결과값이다.

(bzz -> c > ca)

 

그런데 우리가 완전 탐색을 통해 위 문제를 해결하려고 하면 시간초과가 발생한다.

비밀번호의 크기인 N인 최대 10까지 가능하다고 했는데,

이는 26^10 + 26^9 + 26^8 + ... 26^1 의 경우의 수를 가지기 때문이다.

 

26^10만 해도 141,167,095,653,376(약 141조)이라는 값으로

이는 JAVA가 초당 1억번의 연산을 수행한다고 했을 때, 약 1,411,670초(약 392시간)가 걸린다.

 

따라서 모든 경우의 수를 일일이 비교하여 구하지 않고

위에서 찾은 수식을 사용하여 순서를 알아내야한다.

 

제출코드

import java.io.*;

public class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String objective = br.readLine();

        long count=0;
        for(int i=0;i<objective.length();++i){
            if('a'<objective.charAt(i)){
                for(int k=1;N-i-k>0;++k){
                    count+=Math.pow(26,N-i-k)*(int)(objective.charAt(i)-'a');
                }
                count+=(int)(objective.charAt(i)-'a');
            }
            ++count;
        }

        bw.write(count+"\n");
        bw.flush();
        bw.close();
    }
}