2533_사회망서비스 (메모리초과,재귀오류?)

https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

 

문제는 이전 글에서 풀었던 문제와 유사하게 풀 수 있었다.

 

 

역시 트리의 밑에서부터 순차적으로 진행 할것이다.

 

즉, 예제에서 준

 

다음과 같은 트리라면

 

5>6>2>3>7>8>4 순서로 탐색을 하게 될 것이다.

 

이때 검색하는 노드가 얼리어답터라면 그 자식 노드들은 모두 얼리어답터면 안된다.

얼리어답터가 아니라면 그 자식 노드들은 모두 얼리어답터여만 한다.

 

즉 이전 글의 점화식과는 조금 다르게,

 

얼리어답터 X -> 자식의 얼리어답터거아 아니거나 어찌되었든 얼리어답터 수가 적은 것

얼리어답터 O -> 자식이 모두 얼리어답터여야 한다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
tree = [ [] for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

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

def dfs(node):

    visited[node] = 1
    dp[node][1] = 1
    for i in tree[node]:
        if not visited[i]:
            dfs(i)
            dp[node][1] += min(dp[i][0],dp[i][1])
            dp[node][0] += dp[i][1]
dfs(1)
print(min(dp[1][0],dp[1][1]))

 

 

다만 평소대로 pypy3로 시도했는데 재귀오류가 났다...

 

sys.setrecursionlimit(10**5)를 적용해 봤더니 메모리 초과가 났다...

 

인터넷을 조금 검색해보니 python3로 통과시키면 메모리 초과가 나지 않는다고 해서 봤더니 또 재귀오류가 났다..

 

결국 위처럼 sys.setrecursionlimit(10**6)으로 하고 python3로 설정했더니 잘 통과되었다.