[코드그라운드 연습문제] 새로운 방

새로운 방

문제

(1,1)에서 (n,n)으로 최단거리로 이동하고, 만나는 방의 모든 돈을 곱해서 6진수로 변환할 때 뒤에서 부터 연속된 0의 갯수의 최대값을 구하는 문제이다.

문제 풀이

최단 거리로 이동하므로, 아래 또는 오른쪽으로만 이동 가능하다. 따라서 동적계획법을 적용할 수 있고, 결국 (n,n) 방에 도착 하고 소인수 분해 하였을 때 min(2의 개수, 3의 개수) 의 최대값을 구하는 문제로 바뀐다. 한 방에 3은 최대 6개 들어 갈수 있고 (n,n) 에서 최대 6만개 까지 존재 할수 있으므로 \(O(N^2 * 60000)\) 으로 해결 가능하다.

\( dp[i][j][k]=\: i\: 행\: j\: 열에서\: 현재\: 까지\: 모은\: 3이\: k\: 개\: 일\: 때\: 최대로\: 모을\: 수있는\: 2의\: 개수 \)

\( mat[i][j] =\: i\: 행\: j\: 열에서\: 2의\: 개수,\: 3의\: 개수 \)

\( dp[i][j][k]= max(dp[i-1][j][k-mat[i-1][j].second]+mat[i-1][j].first, dp[i][j-1][k-mat[i][j-1].second]+mat[i][j-1].first) \)

k를 그냥 배열로 선언하면 의미없이 메모리를 많이 차지하기 때문에 map컨테이너를 사용하여 구현하였다.

 

소스 코드