BOJ 15811번: 복면산?!

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

15811번: 복면산?!

DFS 재귀를 이용해서 구현을 했는데 시간초과가 났다. 아예 처음부터 순열을 구해서 부르트포스로 풀면 되는 문제였다.

처음에 접근할 때는 넣을 때부터 덧셈의 결과를 맞춰보려고 생각하다가 막혔는데.. 너무 어렵게 생각했던 것 같다. 각 문자마다 다른 숫자여야 하므로 전체 문자의 개수를 구해 0~9까지 그 개수에 맞게 순열을 뽑으면 된다.

 

python은 시간초과.. pypy로 통과했다. 숫자가 주어졌을 때 자리수에 맞춰서 합치는 방법을 잘 기억해놓고.. 제발 for i in range 할 때 range 빼 먹지 말자... 하..

 

import sys
from itertools import permutations
input = sys.stdin.readline

a, b, c = input().split()
alphabet = sorted(list(set(a+b+c)))

num = [x for x in range(10)]
score = [-1]*26
flag = False

for k in permutations(num, len(alphabet)):

    for i in range(len(alphabet)):
        score[ord(alphabet[i])-65] = k[i]

    A = B = C = 0
    
    for i in range(len(a)):
        A = A*10 + score[ord(a[i])-65]
        
    for i in range(len(b)):
        B = B*10 + score[ord(b[i])-65]
        
    for i in range(len(c)):
        C = C*10 + score[ord(c[i])-65]

    if (A+B == C):
        print('YES')
        flag = True
        break
if (flag==False):
    print('NO')