흙금이네 블로그

[BOJ] 2482 - 색상환 (Python) 본문

알고리즘

[BOJ] 2482 - 색상환 (Python)

흙금 2023. 4. 13. 14:59

 

 

아이디어

 

동적 계획법으로 서로 인접하지 않은 색을 고를 수 있는 경우의 수를 구한다.

 

 

풀이

 

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()

 

'알고리즘' 카테고리의 다른 글

[BOJ] 1865 - 웜홀 (Python)  (0) 2023.04.14
[BOJ] 1019 - 책 페이지 (Python)  (0) 2023.04.13
[BOJ] 12886 - 돌 그룹 (Python)  (0) 2023.04.13
[BOJ] 3108 - 로고 (Python)  (0) 2023.04.13
[BOJ] 16954 - 움직이는 미로 탈출 (Python)  (0) 2023.04.13
Comments