26981 [BOJ] 2698번: 인접한 비트의 개수 https://www.acmicpc.net/problem/2698 D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수 처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다. 마지막 비트가 0일 때 D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1] 마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다. ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다. 마지막 비트가 1일 때 D[n][k][l.. 2018. 8. 7. 이전 1 다음