백준 2698번 파이썬 문제풀이(인접한 비트의 개수) - DP(탑다운)

---

DP개념 익히기 좋은 문제이나 사실 3차원 DP를 처음부터 생각하기란 쉽지 않다.. DP의 형태를 보면 depth -> 현재 이어붙인 숫자의 개수, cnt -> 인접한 비트의 개수, cur -> 현재의 비트(0,1) 형태로 되어있다.여기서 DP개념을 이용하자면 어느 한지점(depth) 에서 내가 현재 구한 숫자의 개수(cnt)를 가지고 현재의 비트(cur)에서 구할 수 있는 개수를 저장해놓으면 어차피 다른 재귀가 해당 지점에 도착했을 시 이미 구한 개수를 이용하면 된다. 이러한 개념이 DP인데 다음의 코드를 잘 분석하면 된다.

def dfs(depth, cnt, cur):
    if depth == N:
        if cnt == K:
            return 1
        else:
            return 0

    if dp[depth][cnt][cur] != -1:
        return dp[depth][cnt][cur]

    dp[depth][cnt][cur] = 0

    dp[depth][cnt][cur] += dfs(depth + 1, cnt, not cur)
    dp[depth][cnt][cur] += dfs(depth + 1, cnt + (cur * cur), cur)

    return dp[depth][cnt][cur]


T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    dp = [[[-1, -1] for _ in range(101)] for _ in range(N + 1)]
    print(dfs(0, 0, 0))