[BOJ/백준] 10421 수식 완성하기

이 문제는 데이터 수정이 있기 전까지 안 풀기 를 권장합니다.

 

이 문제를 푸실분들은 https://www.acmicpc.net/board/view/69371 이 글을 참조하거나

 

밑의 input을 받는 방식으로 받기를 권장합니다.

 

import sys
from itertools import product
def input():
    return sys.stdin.readline().rstrip()

def dfs(first_num,idx,total):
    global result
    if idx == line_cnt[1]:
        str_total = str(total)
        str_set = set(str_total)
        if len(str_total) == line_cnt[idx+2] and not (str_set-total_num):
            result += 1
    else:
        for k in int_total_num:
            temp = k*first_num
            str_temp = str(temp)
            str_set = set(str_temp)
            if len(str_temp) == line_cnt[idx+2] and not (str_set-total_num):
                number_of_digit = 10**idx
                temp_num = temp * number_of_digit
                dfs(first_num,idx+1,total+temp_num)


N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
line_cnt = list(map(int,list_))
number_list = list__[:]
total_num = set(number_list)
int_total_num = set(map(int,number_list))
result = 0
for num_line1 in product(number_list,repeat=line_cnt[0]):
    first_line_num = int(''.join(num_line1))
    dfs(first_line_num,0,0)


print(result)

 

이 문제의 아이디어 자체는 그리 어렵지 않다.

 

모든 것을 다 구해보면 된다.

 

하다가, 안되는 경우가 발생하면 되돌아가서 새로운 걸 하면 된다.

 

저같은 경우엔 첫줄의 숫자는 product를 이용해 구했다.

 

그리고 두번째 숫자부터는 직접 중복순열을 해주면서, 중간에 모든 조건을 만족해야지만, 그 다음 조건으로 갈 수 있게 해주었다.

 

그리고 주어진 숫자가 있는지 없는지는 차집합을 통해 길이가 0이면 전부 있는것이므로, 길이가 0인경우에만 통과시켜줬다.

 

 

import sys


def input():
    return sys.stdin.readline().rstrip()

def choose_1(idx,val):
    global K
    if idx == line_cnt[0]:
        choose_2(0,0,val)
        return
    else:
        for i in range(K):
            choose_1(idx+1,val*10+number_list[i])
def check_length(val):
    val = str(val)
    return len(val)
def check_number(val):
    while val:
        if not number_visit[val%10]:
            return False
        val = val//10
    return True

def choose_2(idx,val,first_num):
    global K,result
    if idx == line_cnt[1]:
        last_num = first_num * val
        if check_length(last_num) == line_cnt[-1] and check_number(last_num):
            result += 1
        return
    else:
        for i in range(K):
            if check_length(first_num*number_list[i]) == line_cnt[idx+2] and check_number(first_num*number_list[i]):
                choose_2(idx+1,val*10+number_list[i],first_num)

N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
result = 0
line_cnt = list(map(int,list_))
number_list = list(map(int,list__))
number_visit = [False for _ in range(10)]

for num in number_list:
    number_visit[num] = True


choose_1(0,0)

print(result)

이 방식은 좀 더 깔끔한 방식인것같다.

 

여기는 나머지를 이용해서 각 자리수를 구하고, 그때 숫자가 있는지 없는지는 리스트의 방문표시로 해주었다.

 

길이는 문자열로 바꾼뒤 그 길이를 구해주었다.

 

이 방식이 좀 더 깔끔한 코드라 생각한다.