[백준 12928번] 트리와 경로의 길이 (Python3)

N,S = map(int,input().split())
comb = [i*(i+1)//2 for i in range(N)]
DP = [set() for i in range(S+1)]
DP[0] = {(i,i) for i in range(N+1)}
for i in range(N):
  c = comb[i]
  for s in range(1,S+1):
    if s-c<0:
      continue
    for n,cnt in DP[s-c]:
      if n+1<=N and cnt+i+1<=2*N-2:
        DP[s].add((n+1,cnt+i+1))
print(int((N,2*N-2) in DP[S]))

다이나믹 프로그래밍으로 해결하였다.

 

풀이를 설명하면,

1. 간선의 개수는 N-1개이다. 즉 각 노드에서 연결된 노드의 합은 2N-2이다.

2. 어떤 노드에 연결된 노드의 개수가 x개일 때, 해당 노드를 중심으로 하는 길이가 2인 단순경로는 xC2 = x*(x-1)/2개이다.

3. 어떤 노드에 연결된 노드의 개수가 1~N개일 때 단순경로의 개수를 comb에 계산해둔다.

4. 냅색알고리즘과 비슷한 방식으로 2중 for문을 돌면서 단순경로의 수를 저장한다. 이때 DP에는 (n,cnt)의 튜플로 저장하는데, 노드의 개수를 cnt는 연결의 개수를 의미한다.

5. DP[S]에 (N,2N-2)가 들어있는지 여부를 출력한다.

 

전체적으로 냅색 알고리즘과 비슷한 방식이다. 사실 변수가 여러개다보니 DP를 2차원으로 만들었어야 했는데, 복잡하다보니 그냥 간단하게 튜플과 셋을 이용했다. 코드는 좀 더 간략하지만 시간적인 측면에서 성능이 다른 풀이에 비해 다소 떨어졌다.

 

 

오늘의 교훈) 2차원 DP로 성능을 개선시키는 방법도 고려해보자