흙금이네 블로그

아이디어 동적 계획법으로 서로 인접하지 않은 색을 고를 수 있는 경우의 수를 구한다. 풀이 def solution(): N = int(input()) K = int(input()) p = 1000000003 if K > N//2: print(0) return dp = [[0]*N for _ in range(N//2+1)] dp[1] = [1]*N for i in range(2, N//2+1): for j in range(N-3): dp[i][j+2] = (dp[i][j+1]+dp[i-1][j])%p dp[i][-1] = dp[i][-2] res = 0 for j in range(N): res = (res+dp[K][j])%p print(res) solution()