[백준] 16968번(python 파이썬)

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

 

백트래킹 관련 문제여서 백트래킹으로 풀었는데 생각해보면 경우의 수를 구하는 문제라 백트래킹으로 풀지 않아도 된다

 

중복 형식일경우 경우의 수를 체크해주면된다..

 

ex) dd : 10*9     ddd: 10 * 9 * 10

     cc : 26 * 25     ccc: 26 * 25 * 26

     cdc : 26 * 10 * 26

 

이런식....

car_number = list(input())
result = 0

def BackTrack(depth, dup):
    global result
    if depth == len(car_number):
        result += 1
        return

    if car_number[depth-1] != car_number[depth]:
        dup = -1

    if car_number[depth] == 'c':
        temp = [False] * 26
        for i in range(26):
            if dup != -1:
                temp[dup] = True
            if temp[i]:
                continue
            BackTrack(depth + 1, i)

    else:
        temp = [False] * 10
        for i in range(10):
            if dup != -1:
                temp[dup] = True
            if temp[i]:
                continue
            BackTrack(depth+1, i)

def solve():
    global result

    for i in range(len(car_number)):
        if car_number[i] == 'c':
            if i == 0:
                result *= 26
                continue
            if car_number[i - 1] != car_number[i]:
                result *= 26
            else:
                result *= 25
        else:
            if i == 0:
                result *= 10
                continue
            if car_number[i - 1] != car_number[i]:
                result *= 10
            else:
                result *= 9

#BackTrack(0, -1)
result = 1
solve()
print(result)