글 읽기 - 메모리 초과가 나오는 이유가 궁금합니다. 제가 불필요한 코드를 넣었나요?

yjh77357 2년 전 0

논리적으로 필요한 부분들만 남겼다고 생각했는데 계속해서 메모리 초과가 발생합니다. 좋은 모듈들이 있는데 리스트 반복문으로 무식하게 풀어서 이런지, 아니라면 제가 그리디 알고리즘을 더 공부해서 알고리즘을 새로 짜야할지 궁금합니다!

n, k = map(int, input().split())

# 모든 회사들의 리스트
C_list = []

for i in range(n):
    s = int(input())
    C_list.append(s)

#인접한 회사 간 길이의 리스트 / 인접한 회사들의 리스트
L_list = []
duo = []

for j in range(len(C_list) - 1):
    L_list.append(C_list[j+1]-C_list[j])
    duo.append([C_list[j], C_list[j+1]])

# 인접한 회사 쌍들과 그 거리를 묶은 리스트
All = list(zip(duo, L_list))

# 조합combination을 통해 가능한 회사 쌍들의 조합을 모두 생성
import itertools
result = list(itertools.combinations(All, k))


#회사 쌍들의 조합에서 중복된 회사가 없도록 비교 후 중복요소 제거하기 위한 절차
import copy

for i in result: # i는 k개의 회사 쌍의 조합
    for j in i: #j는 각 회사 쌍과 회사 사이 거리
        B = list(copy.copy(i)) #리스트 모듈의 remove를 쓰기 위해 복사본 생성, 리스트화
        B.remove(j) #회사쌍 조합을 복사한 뒤 특정 회사쌍을 제거
        for exc in B:
            if set(j[0]) & set(exc[0]) != set(): #만약 제거된 회사쌍과 남아있는 회사쌍에 중복이 있다면
                while result.count(i)>0:
                    result.remove(i) #중복요소가 없을 때까지 제거
            
#가능한 모든 최종 케이블 거리들의 리스트를 만든 뒤 최소값을 출력
lengs = []
for i in result:
    leng = 0
    for j in i:
        leng += j[0][1]-j[0][0]
    lengs.append(leng)
print(min(lengs))

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

문제

문제

출처

ICPC

메모리 초과가 나오는 이유가 궁금합니다. 제가 불필요한 코드를 넣었나요?

yjh77357 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말