[질문] 2482 색상환같은 문제 접근을 어캐함??

[익명(110.70)]

dp라는데 내가 너무 할줄 모르는건가? 접근도 못하겠는데

- dc official App

[시아닌(kimjg1119)]

원형을 잘라서 일자로 바꾸면 쉬움

[익명(175.223)]

라는 생각을 못하겠음 좀 어렵다 싶은 dp는 다 그래 - dc App

[시아닌(kimjg1119)]

그냥 원형 나오면 무조건 자르면 됨 이런건 많이 풀다보면 느낌옴

[익명(175.223)]

양의문제인가보다 ㄱㅅ - dc App

[하루룽(ailedear)]

일단 선형이라 생각하고 DP를 짜셈 선형에서 n개중 k개 고르는 경우의 수를 dp[n][k]라 하면

[하루룽(ailedear)]

원형에서 N개중 K개 고르는 경우의 수 (원래 문제) 는 dp[N-3][K-1] + dp[N-1][K] (각각 N번째 칸을 골랐을 때와 안 골랐을 때)

[익명(175.223)]

선생님 친절한 설명 감사합니다. 일단 선형이라고 생각하는걸 발상하는게 어렵네요 - dc App