SWEA 7673 - 영이는 영이 시져시져!

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_

문제

경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.

trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.

이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.

가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,

다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.

항상 위쪽 또는 왼쪽까지 도착한 경로 중에서, 0의 개수가 최소가 되는 경로를 선택하면 됩니다.

다익스트라를 써도 되고, DP를 써도 풀립니다. 대신 다익스트라가 조금 더 오래 걸리네요.

코드

비슷한 문제

• BOJ 10164 - 격자상의 경로
• 오른쪽 또는 아래쪽으로만 이동하는 점에서 이 문제와 상당히 비슷합니다.
• algospot - 삼각형 위의 최대 경로 수 세기
• 아래 또는 오른쪽 아래로 이동하며, 최대 합을 세는 문제입니다.