나무 조경
Prob
초기 격자의 상태가 주어졌을 때 최대 4개의 쌍을 겹치지 않게 골라 얻을 수 있는 나무의 키의 합의 최댓값
격자의 크기 n
2 ≤ n ≤ 4
1 ≤ 나무의 키 ≤ 10
Solv
n==2 일때는 무조건 2쌍의 합이 최댓값이므로 모든 원소의 합
n==3 일때 쌍이 없는 원소가 정중앙, 모서리에 올 경우로 나뉨
따라서 n==3부터는 하나의 쌍이 주어졌을 때 다른 쌍이 추가되는 경우를 생각해야하므로 dfs, 백트래킹 사용
dfs 수행 시 next는 항상 오른쪽과 아래만 가능
Check
2 1 3 3
5 1 2 1
2 1 2 3
5 1 1 1
tmp = tmp + now + next
| depth | ans | tmp | now | next |
|---|---|---|---|---|
| 0 | 0 | 2 | 1 | |
| 1 | 3 | 3 | 3 | |
| 2 | 9 | 5 | 1 | |
| 3 | 15 | 2 | 1 | |
| 4 | 18 | 18 | 2 | 2 |
| 4 | 20 | 20 | 2 | 2 |
| 3 | ||||
