글 읽기 - 2533번 사회망 서비스 메모리초과

dldnjsrl 3년 전 1

메모리 기준이 예전보다 빡세진건가요..? 계속 메모리초과 떠서, 블로그의 통과 코드를 집어 넣어봐도 메모리초과가 발생하네요...

아래의 소스 코드에서 어떻게 메모리를 줄여야 할까요....

# 2533번: 사회망 서비스(SNS)
import sys
sys.setrecursionlimit(10**9) 

def getChildList(node):
    visited[node] = True
    for i in link[node]:
        if not visited[i]:
            child[node].append(i)
            getChildList(i)
            
def sol( node, isEarlyadopter ):
    if isEarlyadopter: #  해당 Node가 earlyadopter라면
        if dp[ node ][ True ] == -1:
            result = 1 # 자신이 earlyadopter임으로 1로 시작
            for childNode in child[node]:                    
                if len( child[childNode] ) == 0 : result += 0 # child가 leaf노드
                else: result += min( sol(childNode, True), sol(childNode, False) )
            dp[ node ][ True ] = result
        return dp[ node ][ True ]
    
    else: # 해당 Node가 earlyadopter가 아니라면
        if dp[ node ][ False ] == -1:
            result = 0
            for childNode in child[node]:
                if len( child[childNode] ) == 0 : result += 1 # child가 leaf노드
                else: result += sol(childNode, True) # 자기가 earlyadopter가 아님으로, child node가 모두 earlyadopter여야함.
            dp[ node ][ False ] = result
        return dp[ node ][ False ]
###############################################################################################################
N = int(input())
link = [ [] for i in range(N) ]
for _ in range(N-1):
    u, v = list(map(int, input().split()))
    link[u-1].append( v-1 )
    link[v-1].append( u-1 )

child = [[] for i in range(N)]
visited = [False] * (N)
getChildList( 0 )

del link, visited
dp = [ [-1,-1] for i in range(N) ]
result = min( sol(0, True), sol(0, False) )
print( result )

diamondcubic 3년 전 1

저도 Python, PyPy 다 메모리 초과 떠서 울고 있었는데, C++로 똑같이 짜니까 통과하네요. ㅠㅠ

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dfs(i):
    visited[i] = 1
    dp[i] = [0, 1]
    for j in graph[i]:
        if not visited[j]:
            dfs(j)
            dp[i][0] += dp[j][1]
            dp[i][1] += min(dp[j])


n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dp = [[0, 0] for _ in range(n + 1)]
visited = [0] * (n + 1)
dfs(1)
print(min(dp[1]))

pepper_mis 2년 전 1

혹시 PyPy3로 제출하셨으면 Python3으로 제출해보세요!

저는 같은코드로 전자는 메모리초과, 후자는 통과됐어요.

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

문제

문제

출처

ICPC

2533번 사회망 서비스 메모리초과

dldnjsrl 3년 전 1

diamondcubic 3년 전 1

pepper_mis 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말