[BOJ] 16968 차량번호판1 python

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

16968번: 차량 번호판 1

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

 

해설

조건에 맞는 모든 경우의 수를 출력하는 브루트 포스 문제로 재귀적으로  구현했다.

패턴을 하나씩 제거하면서 번호판 길이를 하나씩 늘려갔으며 패턴이 존재하지 않으면 answer에 +1 하는 방식으로 해결했다.

import sys
import string

input = sys.stdin.readline

d_list = [str(i) for i in range(10)] # 숫자 리스트 
c_list =[c for c in string.ascii_lowercase] #영어 소문자 리스트
pattern = input()
answer =0

#가능한 모든 경우의 수를 찾아준다.
def choose(pattern, result):
	
    global answer
    # 더 이상 패턴에 존재하는 숫자가 없다면 번호판이 완성되었음
    if not pattern:
        answer += 1
        return
    
    i = pattern[0]
    #입력할 패턴이 숫자라면
    if i == 'd':
    	# 숫자리스트에서 하나를 뽑는다.
        for d in d_list:
        	#현재 번호판에 입력된 값이 없으면 
            if not result: #무조건 값을 입력
                choose(pattern[1:], result + d)
            
            #아니라면
            else: 
            	마지막으로 입력된 값과 비교해서 다르면 값을 입력
                if result[-1] != d:
                    choose(pattern[1:], result + d)
                    
    #숫자의 경우와 동일하게 수행한다
    elif i == 'c':
        for c in c_list:
            if not result:
                choose(pattern[1:], result + c)
            else:
                if result[-1] != c:
                    choose(pattern[1:], result + c)

choose(pattern, '')
print(answer)