[알고리즘 문제 풀이][조합] 백준 17205번 - 진우의 비밀번호

백준 17205번 진우의 비밀번호 문제입니다.

(조합론)

 

- 문제 설명: https://www.acmicpc.net/problem/17205

- 문제 풀이:

 

가능한 비밀번호가 최대 3자리라면 a, aa, aaa, aab, aac, ..., azy, azz, b, ba 이런 식으로 나타나게 됩니다.

그러면 매 자리마다 가능한 경우의 수를 합해주면 됩니다.

 

a

b

...

z

===> 여기가 총 26개

a a

a b

a c

a ...

a z

====> 여기는 a~z * a~z 를 생각하면 총 26 * 26개

a a a

a a b

a a c

a a ...

a a z

======> 여기는 a~z * a~z * a~z 를 생각하면 총 26 * 26 * 26개가 됩니다.

 

그렇다면 만일 최대 길이가 3이고, 문제에서 주어진 첫 번째 자리가 b 라면, b 전까지의 경우의 수는 a 로 시작하는 모든 3가지 경우일 것입니다. a / a a ~ a z / a a a ~ a z z 까지가 모두 해당할 것입니다.

 

따라서 a 인 1개 + 26 * 26 개 + 26 * 26 * 26 개를 우선 더해주어야 합니다.

 

그 다음에는 다음 자리에 가서 똑같이 고려를 해주어야 합니다. 만일 두 번째 자리가 c 라면 (그래서 비밀번호가 bc 라면), 맨 앞 자리는 b 로 고정하고 두 번째 자리부터 고려했을 때 가능한 경우는 a ~ b / a a ~a z 와 b a ~ b z 가 해당될 것입니다. 그러면 a, b 로 2개 + 26 * 26개 * (a, b 2개) 로 구할 수 있습니다.

 

이를 일반화하면, 각 자리마다 이전 알파벳까지 가능한 등비 수열의 합 (26 + 26 * 26 + 26 * 26 * 26 ...) 과 이전 알파벳의 개수를 합해주면 됩니다. 예를 들어, 위의 bc 예시에서, 첫번째 자리는 1개 + 1개 * (26 부터 시작하는 등비수열의 합) 입니다. 두번째 자리는 2개 + 2개 * (26 부터 시작하는 등비수열의 합) 이 됩니다.

 

(텍스트로 적어서 복잡해보이지만, 가능한 경우를 세로로 쭉 써보다보면 규칙성을 조금 더 쉽게 파악할 수 있습니다.)

 

- 코드: 

N = int(input())
pwd = input()
ans = 0
anum = ord('a')
N -= 1
for alpha in pwd:
    diff = ord(alpha) - anum
    if diff > 0:
        ans += (diff)*26*(26**N-1)//(25) + diff
    ans += 1
    N -= 1
print(ans)

 

- 실수 포인트 & 반례:

1. 본 문제는 별다른 반례가 없습니다. 1자리의 경우가 잘 커버 되는지 확인하기 위해 아래 예시를 넣어보면 좋습니다.

입력)
1
a

정답)
1

입력)
1
c

정답)
3