BOJ 9457 - 기하학문양
대충 점화식을 찍어서 맞았다.
$dp[i][c]$ 를 정의하고, $dp[i][0]$ 은 $i$번 째 column을 볼 차례인데 $i$ 의 두 정점이 트리에서 연결되지 않은 상태의 경우의 수이고 $c=1$이면 연결된 상태의 경우의 수라고 하자.
$dp[1][0]=dp[1][1]=1$ 으로 초기화해둔다.
이제 $i=2$ 부터 다음과 같은 점화식이 성립한다.
c = 0
일단 $i-1$ 에서도 두 정점이 연결되어 있지 않으면 항상 두 간선을 이어줘야 하기 때문에 $dp[i-1][0]$을 더해줘야 한다.
연결되어있다면 위로 하나만 이어주거나 아래로 하나만 이어줘야 하기 때문에 $2$가지의 경우가 있다. 따라서 $2dp[i-1][1]$ 을 더해준다.
c = 1
$i-1$ 에서 두 정점이 연결되어 있지 않으면 항상 위아래 두 간선을 이어줘야 하고, $i$ 번째의 두 정점도 이어줘야 하기 때문에 $3$개의 간선을 추가하는 한 가지 경우만 있다. 그래서 $dp[i-1][0]$ 을 더해준다.
트리에서 싸이클이 생기지 않게하기위해
- 위 아래로만 두 간선을 잇는 경우
- ㄱ 자로 위와 $i$ 번째 두 정점을 잇는 경우
- 반대로 아래와 $i$번째 두 정점을 잇는 경우
해서 $3dp[i-1][1]$ 을 더해줘야 한다.
이렇게 하면 원형이 아닐때의 정답이 구해진다.
직선일 때의 정답은 $dp[n][1]$ 이다.
원형일 때의 정답은 이 테이블을 사용해서 얻을 수 있다.
원형일 때 어떤 식으로 선들이 이어지는지 고려해보자.
우선 다음과 같은 경우를 한 가지 고려한다.
어떤 인접한 두 column $i, i+1$ 를 잇는 간선이 하나도 없어야 하고, $n$ 개의 후보중 그러한 것이 하나만 등장한다.
따라서 $n \cdot dp[n][1]$ 을 정답에 더해준다.
두 번째 케이스
$dp[n][0]$ 은 $n$ 번째의 두 정점이 트리에서 이어지지 않은 케이스이다.
이걸 $1$ 번째 정점과 이어줘보자.
모르겠다 ㅈㅅ
Comments