[코드그라운드 연습문제] 새로운 방
새로운 방 문제 (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\: 개\: 일\: 때\: 최대로\: 모을\: 수있..
PS/Codeground
2017. 4. 10. 19:34