행렬에서 붙어있는 연속한 숫자들 중 가장 긴 조합 찾기 Q

행렬에는 1 ~ N^2 의 서로 다른 숫자로 구성되어 있다..

ex)

1 5 9

2 3 8

4 6 7

>> ans : 6 7 8 9

풀이 : 각 점에 대해 연속된 숫자가 주위에 있는지 확인한다. 재귀적으로 따라간다. 길이가 최대보다 길면 기록한다.

크게 재귀가 많이 일어나지는 않을 것으로 보이고 풀고 나면 DP 캐핑이 될 것 같기는 하다.

참신한 최선 풀이

vector<bool>(N^2,false) 에다가 i이 i-1 과 붙어있는가? 의 값을 찾아서 채운다.

최종적으로 이 불리안 어레이의 true가 가장 긴 부분이 정답이다.

https://www.careercup.com/question?id=5147801809846272