[platinum3][해설안봄,알고리즘 분류 안봄] 1533 길의 개수

이번 문제는 상당히 애를 먹었던 문제였다, 일단 유형도 처음보는 유형이고, 힌트를 안보고 풀다보니 나름 기발한 아이디어를 떠올렸다고 생각했지만 푼 후기들을 보니 다들 비슷하게 푼거같은... 역시 사람 생각은 다 비슷비슷하구나를 느끼게 된 그런 문제였다.

 

https://www.acmicpc.net/problem/1533

 

 

단순 dp처럼 보이지만 문제는 T가 10억 이하라는 것이다.

우선 가장 문제풀이의 기초가 되는 생각은 dp[현재위치][현재까지의 시간] = 가능한 길의 종류 개수 총합 = Sum(dp[이전위치][이전까지의 시간])

 

 

시작점이 1 이므로 dp[1][0] = 1 이다.

 

  dp[3][2] += dp[1][0] (1 에서 3으로 가는데 시간 2 소요)

dp[2][1] = dp[1][0] .(1에서 2로 가는데 시간 1 소요)

 

dp[1][3] = dp[3][2] + dp[2][1] = 2 

 

이런식으로 생각해 볼 수 있다.

 

처음에 O(10억 * N * N ) 을 어떻게 처리할 까 고민하다가, dp긴 dp인데 기존의 dp는 가중치가 랜덤하게 바뀌는 (예를 들면 dp[T] = Wi * dp[T - Ti] 와 같이  i에 따라 랜덤하게 Wi 와 Ti 값이 주어지는... )그런 dp라면 진짜로 10억이라는 수를 모두 처리해야 겠지만 이 문제에서는 인접행렬에 따라 규칙이 일정하다는 것을 생각해 냈다.

결국 dp[N][T] = dp[1][T - c1] + dp[2][T-c2] + dp[3][T-c3] ... dp[N-1][T- Tn-1]  이런식으로 항상 점화식이 일정한 것이다.

항상 점화식이 일정하다면... 점화식을 일단 한번 구하고, 점화식 계수 (coefficient)를 활용해 더 큰 T에 대한 계수를 또 구할 수 있을 거라고 생각했다.

 

 예를 들어  기본적으로  시간T이 0 ~ 4 까지의 dp 값들이 있다면,  이 값들로 T 5 ~9 까지의 값들을 점화식을 구해 구할 수 있다.

dp[1][5] = 2 * dp[2][1] + 3 * dp[2][2]..

dp[2][7] = 1 * dp[3][2] + 3 * dp[3][4]..  이런식으로 나타낼 수 있을 것이다

 

 

 

마찬가지로 T:10~14에서도 T:5~9 까지의 값들에 대해 서 나타낼 수 있다,

dp[1][10] = 2 * dp[2][7] + 3 * dp[2][8]..

dp[2][14] = 1 * dp[3][7] + 3 * dp[3][8]..  이런식으로 나타낼 수 있을 것이다 (이해를 위해 임의로 나타낸 것이고 계산을 해보진 않았다)

 

그런데 아까 T0~4 들의 dp값으로 T5~9 의 값들을 표현했으므로, 

T:10~14 의 값들 :T0~4의 값들로 표현 가능

-> 여기서 T를 10씩 더하면  -> T:20~24의 값들도 T:10~14의 값들로 표현 가능 -> 결국 T;20~24의 값들은 T0~4로 표현 가능

-> T를 20씩 더하면 ->T:40~44 : T20~24로 표현가능 -> T:40~44 : T 0~4로 표현 가능.

 

저렇게 표현 가능한 범위가 10 ~ 20 ~ 40 씩 늘어나는 것을 볼 수 있다. 

결국 계수값만 잘 구해내면 2^n의 크기로 금방 구할 수 있는 것을 알 수 있다. 2^30 은 10억에 근접하므로, O(30 )

 

 

처음에 이걸 발견하고 생각한 건 map 을 잘 활용하면 해결할 수 있겠다고 생각했다.

static Map<String,Map<String,Integer>> coMap = new HashMap<String, Map<String,Integer>>();

이런형태로

 coMap의 key String에는 길의종류: 지난시간 의 형태로 넣고, 안쪽의 map에는 key로 길의종류:지난시간 , value로는 계수를 넣으면 된다고 생각하였다.    dp[1][10] = 2 * dp[2][7] + 3 * dp[2][8] 일때 coMap 의 key는 1:10, 안쪽Map은 {2:7,2} , {2:8,3} 이런식으로 말이다.

Map을 사용해 위의 설명한 내용들을 구현하면 가능하다고 생각하였는데 생각보다 구현이 너무 까다로웠다.

그래서 다른 방법이 없나 생각하던 도중 편입시절 선형대수학에서 행렬을 사용하던게 생각이 났다. 여러 변수가 잇는 수열에서 계수들을 행렬로 나타내고, 행렬의 곱으로 수열의 항들을 정리하던 그런 뉘앙스(이걸 배웠는지는 잘 모르겠지만) 가 떠올라서, 혹시 이런 반복적인 점화식에서 행렬로 구할 수 있지 않을까 하는 기대감이 들었다.

 

 그런데 편입 시절 외에는 거의 선형대수학을 놓고 있던 차라 어떻게 이걸 표현할지 애를 먹고 있던 찰나에 각 행렬을 길의 종류로만 표현하지 말고, 0~5까지 정도의 시간도 같이 표현하면 어떨까 하는 생각이 들었다. 

대충 이런식으로... (a는 현재위치가 1, b는 2 , c는 3.. 문자뒤의 숫자는 현재 시간을 의미) 나타내보았다.

위의 행렬을 제곱해보았더니 4번째 줄에다가 (b0  , b2, c1 행이 들어오는 것을 알 수 있었다. (이 성질을 알기까지도 꽤 오랜시간이 걸렸다..)  결국 제곱을 하면  a3 = b0 + b2 + c1   일때 b0,b2,c1의 값들도 들어올 수 있는 것이다 (b2의 경우 a0 + c0) 

이런식으로 행렬을 제곱하면 다음 행렬의 점화식을 구할 수 있다는 것을 알게 되었다.

이 성질을 이용하면 현재가 N이라면 행렬A를 통해 N+5 를, A^2을 통해 N + 10 을, (A^2)^2 을 통해 N+20을... 구할 수 있는 것을 알 게 되었지만, 문제가 있었다.

 

a0행, b0 행  과 같은 행들은 열의 값들로 (a0,a1,a2....c5) 표현을 할 수 없었다.  이걸 표현 할 수 없으면 제곱을 한다 한들 제대로 식이 세워지지 않을 것이다.

그래서 또 이문제로 오랫동안 고민을 하던 중 어차피 그냥 점화식을 표현 할 수만 있으면 되니까, 행의 값들에서의 시간을 충분히 크게 하면 되지 않을까 라는 생각을 하였고,,

 

     a0 a1 a2 a3 a4 b0 b1 b2 b3 b4 c0 c1 c2 c3 c4 

a5 
a6 
a7 
a8    0   0   0   0   0   1   0  1  0   0  0   0   1  0   0   0   0 
a9  
b5
b6 
b7  1 0  0   0  0   0  0  0  0  0  0 0  0  1
b8 
b9  
c5
c6 
c7
c8 
c9

 

이런식으로 시간을 설정하면, 가장 작은 시간이 5이므로, 충분히  열에서의 시간(0~5) 로 표현이 가능하다. 행에서 최소가 5 이면 열에서의 최대는 4가 될것이므로, (시간이 0인 경로는 없기 때문에 ) 수정하였다.

행렬 한번을 통해서 이제 행의 값은 a10~a14, b10~14... c10~14 가 되고, 2번을 하면 a15~19 ... 가 된다.

 

이제 모든 행의 값들은 열로 충분히 표현 가능하므로, 행렬을 완성 한 뒤, A, A^2 , A^4, A^8 ,.... 등을 제곱으로 구해나가면 된다.

예를들어 T = 400 일때를 구해야 하면  행렬 한번에 5씩 늘어나므로 400 / 5 = 80 -> A^80 을 구해야 한다.

 

제곱으로 구하다가 A^64 까지 구하고, 남은 T= 16 에 대해 A^16 으로 구할 수 있다

(A^16) * (A^64)  로 표현이 가능

 

 

일단 열의 값들은 시간을 0~4까지 설정하였는데 이건 행에 대한 계수를 표현하기 위한 것이였다.  실제로는 a0, b0 값은 없을 수도 있다. 

  이를 해결 하기 위해서 구해야 하는 T= 403이라고 하면 T = 300 까지 구한뒤,  T:300~304 -> T:0~4 에 대해 표현이 가능하게 한다. 그후  고전적인 방법으로(?) T = 104 까지의 값을 구한다.  아까 언급했던 방식대로

 

 

시작점이 1 이므로 dp[1][0] = 1 이다.

 

  dp[3][2] += dp[1][0] (1 에서 3으로 가는데 시간 2 소요)

dp[2][1] = dp[1][0] .(1에서 2로 가는데 시간 1 소요)

 

dp[1][3] = dp[3][2] + dp[2][1] = 2 

 

이런식으로 생각해 볼 수 있다.

 

처음에 O(10억 * N * N ) 을 어떻게 처리할 까 고민하다가, 

 

 

 

T= 104까진  O(10400)이므로 괜찮다.

 

 

 

아까 T:300~304 -> T:0~4로 표현이 가능하게 하였으므로,  여기에 100씩 더하면 T:400~404 -> T:100~104로 표현이 가능하다.

 

이제 T = 403에 대해 값을 구할 수 있게 되었다.

 

T = 100정도로 잡은 건 T 가 부족해서 점화식을 표현하지 못하는 위험을 방지하기 위해 안전하게 잡았다. 사실 T = 10 정도로 더 줄여도 되긴 할텐데 혹시 모르니...

 

 

 

사실 이 문제를 어떻게 풀지 대충 느낌이 온 뒤에도, 구현하는게 처음 코딩해보는 개념이기도 하고, 구현에서 얼마나 많은 노력과 스트레스가 발생할까 감도 안잡혀 고민했지만.. 생각해낸게 아까워 구현했고  천만다행히도 생각한 게 맞았고 구현도 특별히 잘못된 게 없어 약간의(?) 디버깅 끝에 겨우 해결할 수 있었다..

 

 

 

 

 

 

//public static String makeKey(int a, int b) return a + ":" + b;