[Python] 백준 2698번: 인접한 비트의 개수

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

2698번: 인접한 비트의 개수

1. 비트가 0으로 끝날 때와 1로 끝날 때를 나누어준다. 0으로 끝날 때는 같은 행의 이전 열의 합이고, 1로 끝날 때는 이전 열이 0으로 끝날 때 + 이전행 이전 열의 1로 끝날 때 1을 더해준다.

2. 점화식은 dp[i][j][0] = dp [i][j-1][1] + dp [i][j-1][0], dp [i][j][1] = dp [i-1][j-1][1], dp [i][j-1][0]이다

3. 0번째 인덱스부터 접근해야 하기 때문에 배열의 크기를 101로 주었고 max를 준 이유는 초기값이 0으로 초기화됨을 방지하기 위함이다.

import sys
input = sys.stdin.readline

dp = [[[0, 0] for _ in range(102)] for _ in range(102)]
dp[0][1] = [1, 1]

for i in range(101):
    for j in range(i+1, 101):
        dp[i][j][0] = max(dp[i][j][0], dp[i][j-1][1] + dp[i][j-1][0])
        dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][1] + dp[i][j-1][0])

T = int(input())
while T:
    T -= 1
    n, k = map(int, input().split())
    print(sum(dp[k][n]))