[중고딩문제] 이거 최단경로로 시각화나 점화식 안 쓰면 어떻게 풀수있음?

[익명(211.36)]

문제는

1 2 3 4 5 을

모두 중복해서 써서 7자리 수열을 만든다고 할 때,

이웃한 두수의 차이가 1인 수열의 가짓수

점화식이나 최단경로로 일대일 대응 만들어서

푸는 방법은 아는데

노가다나 점화식 최단경로 이용하는거 말고

다른 풀이를 본적 있는거 같거든 혹시 저 이외

방법으로 풀수 있는 애 있어?

[ns(qwer2357)]

결국 점화식 쓰는거긴 하지만 인접행렬 A=[[ 1 1 0 0 0][1 1 1 0 0][ 0 1 1 1 0] [0 0 1 1 1] [ 0 0 0 1 1]]에 대해 I A^6 = A^6의 성분합이 답이긴 함

[익명(211.36)]

그렇구나 고민해서 3by3까지 줄여보기까지 했는데도 계산이 빡세네 행렬로 푸는건 이게 최선인가보다 고맙다~