https://www.acmicpc.net/problem/16878
대부분의 평범한 컴퓨터 공학 학부생은 풀 수 없는 문제로 보인다.
이 문제는 Hertzsprung's problem라는 이름으로 알려져 있으며 원본 문제는 각 열과 행에 킹이 하나만 있게 하면서 서로를 공격할 수 없게 배치하는 경우의 수를 구하는 것이다.
다행히도 OEIS에는 제한 시간 안에 충분히 돌아가는 단순한 점화식을 제공하는데 다음과 같다.
$dp(0) = dp(1) = 1$
$dp(2) = dp(3) = 0$
$dp(4) = 2$
$dp(n) = (n + 1)dp(n - 1) - (n - 2)dp(n - 2) - (n - 5)dp(n - 3) + (n - 3)dp(n - 4) (n \geq 5)$
이 점화식으로 동적 계획법을 짜면 제한 시간 안에 정답을 받을 수 있다.
Hertzsprung's problem에 대해서는 다음 3개의 자료로 공부할 수 있으니 관심 있다면 살펴보도록 하자.
https://arxiv.org/abs/1905.02387v2
On the poset of King-Non-Attacking permutations
A king-non-attacking permutation is a permutation $π\in S_n$ such that $|π(i)-π(i-1)|\neq 1$ for each $i \in \{2,\dots,n\}$. We investigate the structure of the poset of these permutations under the containment relation, and also provide some results on
arxiv.org
What is the number of permutations possible for 5 elements after a change in order (no two adjacent elements remain next to each
Answer (1 of 3): Generalisation The number of permutations of [n] such that each element is not adjacent to its natural neighbour(s) is given by \displaystyle g(n)=n!+\sum_{k=1}^{n-1}(-1)^kf(n,k)(n-k)!\tag*{} with \displaystyle f(n,k)=\sum_{c=1}^{\min(n-k,
www.quora.com
http://egloos.zum.com/glimpses/v/11184263
Hertzsprung's problem
https://oeis.org/A002464The Probability that Neighbors Remain Neighbors After Random Rearrangements / David P. Robbins The American Mathematical Monthly Vol. 87, No. 2 (Feb., 1980), pp. 122-124 http:
egloos.zum.com
'백준 > 수학' 카테고리의 다른 글
| 백준 2381 - 최대 거리 (0) | 2022.07.06 |
|---|---|
| 백준 15965 - K번째 소수 (0) | 2022.05.13 |
| 백준 1402 - 아무래도이문제는A번난이도인것같다 (0) | 2022.04.05 |
| 백준 16563 - 어려운 소인수분해 (0) | 2021.08.23 |
| 백준 10728 - XOR삼형제 1 (0) | 2021.07.27 |
