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로 성능을 개선시키는 방법도 고려해보자