글 읽기 - 재귀함수로 안돌리고 구현했는데 시간초과뜨네요 혹시 개선법이 있을까요

sam65364 1년 전 0

어디서 시간초과가 나는지 궁금합니다. 아니면 재귀함수를 꼭 써야할까요

from itertools import combinations,permutations,product

n = int(input())
## 좋은수열인지 확인해보는 함수
def count(arr):
    for i in range(1,len(arr)//2+1):
        for j in range(0,len(arr)-2*i+1):
            if arr[j:j+i] == arr[j+i:j+2*i]:
                return False
    return True
a = [1,2,3]
ans = 21470000000000000000000

## 모든 조합을 만들지말고 하나씩 추가할때 마다 확인해보기
start = ''
flag = True
for i in range(n):
    idx = 0
    flag = True
    while flag:
        num = ['1','2','3']
        if count(start+num[idx]): # 만약 숫자를 넣었는데 좋은수열이라면
            start = "".join(map(str,start+num[idx]))
            flag = False
        else:
            idx +=1 #다른숫자 넣어
        if idx == 3: # 3개 다 넣었는데 안된다. 문자열에서 마지막꺼 빼고 아닌 거 2개 넣어보기
            last = start[-1] # 마지막꺼
            start = start[:-1] # 하나뺴고
            num.remove(last)
            num.remove(start[-1])
            start += num[0]
            idx = 0
    print(start)
            
print(int(start))       

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

문제

문제

출처

ICPC

재귀함수로 안돌리고 구현했는데 시간초과뜨네요 혹시 개선법이 있을까요

sam65364 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말