https://www.acmicpc.net/problem/17205
17205번: 진우의 비밀번호
진우는 비밀번호 조합을 a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaab, aaaaac, ..., azzzzx, azzzzy, azzzzz, b 순서로 시도한다.
www.acmicpc.net
사용한 알고리즘 : 수학, 중복순열
풀이전략
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();
}
}
