[질문] 백준 2482 대체 왜 틀림???

여기는 내 풀이 설명임...

문제 조건이 원형이 아니라 선형인 경우, 즉 1번부터 N번까지 중 인접한 수를 고르지 않고 K개 고르는 경우를 F(N, K)라고 하자.

1번째 칸을 칠하는 경우에는 3번 칸~(N-1)번 칸을 선형으로 생각하면 F(N-3, K-1)가지 나오고,

칠하지 않는다면 2번 칸~N번 칸을 선형으로 생각하면 F(N-1, K)가지 나옴.

F(N, K)는 중복조합으로 계산하면 (K+1)H(N+1-2K), 정리하면 (N-K+1)C(K)가 나옴

문제에서 구할 건 F(N-1, K)+F(N-3, K-1) 이고, 이걸 정리하면 (N-K)C(K) + (N-K-1)C(K-1) 을 구하면 됨

dp를 통해 미리 0부터 1000까지 이항계수 계산해주고 N, K 입력 받아서 풀릴 줄 알았는데....

이게 왜 틀림?????

블로그 찾아서 설명 들어봐도 내 설명 틀린 데 없어 보이는데...

이해가 안되네...

댓글 0