글 읽기 - [파이썬] 성공했지만 메모리과다

mike1201 5년 전 0

dfs를 이용해 문제를 해결했는데 메모리가 좀 많이 쓰여서... 혹시 줄일 수 있는 방법이 있을까해서 문의드립니다.

import sys
from collections import deque
#f = open('14889.txt','r')
N = int(input())
graph = [[0]*N for _ in range(N)]
all_score = 0
init = set()
for i in range(N):
    init.add(i)
    tmp = list(map(int, input().split(' ')))
    for j in range(N):
        graph[i][j] = tmp[j]
        all_score = all_score + tmp[j]

def choose(N, graph):
    # Define stack
    K = N // 2
    stack = deque([])
    min_score = 10000000000000
    for i in range(K+1):
        stack.append(([i], 1, 0)) # start 팀 구성원, 숫자, 능력치
    whole = []
    while stack:
        ls, n, score = stack.popleft()

        # 조건1. 갯수가 N/2?
        if n == K:
            ls_s = list(init- set(ls))
            score_s = 0
            for i in ls_s:
                for j in ls_s:
                    score_s = score_s + graph[i][j]
            min_score = min(min_score, abs(score-score_s))

        # 조건2. ls[-1]~N
        else:
            for idx in range(ls[-1]+1,N):
                score_ = score
                # 조건3.
                if idx not in ls:
                    ls_ = ls + [idx]
                    for i in ls_:
                        score_ = score_ + graph[i][idx] + graph[idx][i]
                    stack.append((ls_, n+1, score_))

    print(min_score)
choose(N, graph)

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

문제

문제

출처

ICPC

[파이썬] 성공했지만 메모리과다

mike1201 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말