글 읽기 - 1120번 문제 시간초과 질문입니다

jangys0616 3년 전 0

1120번 문제 재귀로 접근해서 풀었는데, 시간초과가 계속 뜨는거 같습니다..

중복된 경우도 연산을 진행해서 if (A in totalList): return; 이 코드를 통해 진행하지 않았음에도

시간초과가 떠서 어떻게 해야될지 몰라서 질문 드립니다!

from sys import setrecursionlimit 
setrecursionlimit(10**9) 

diffCount = 0
totalList = [] # A를 B의 길이 크기만큼 부족한 부분 양SIDE에 '1' 넣은집합
def dfs(A, B):

    if (A in totalList):
        return;

    if len(A) == len(B):
        totalList.append(A)
        return;
    else :
        dfs(A+'1', B)
        dfs('1'+A, B)

inData = input().split()
A = inData[0]
B = inData[1]

if len(A) != len(B): # A < B 일때만
    dfs(A, B) # totalList에 가능한 A의 모든 집합을 저장하는 함수
else:
    totalList.append(A)

diffList = [] # 각 경우의수 별로 차이가나는 count 개수를 저장하는 List

#print('totalList : ', totalList)

for item in totalList:
    diffCount = 0;
    for i in range(len(item)):
        if (item[i] != B[i] and item[i] != '1'):
            diffCount = diffCount + 1;
    diffList.append(diffCount)


print(min(diffList))


# input 값
# adaabc aababbc

# 정답
# 2

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1120번 문제 시간초과 질문입니다

jangys0616 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말