반응형
1369번
-
1369번 : 배열값알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 22. 14:24
https://www.acmicpc.net/problem/1369 1369번: 배열값 첫째 줄에 배열의 크기를 나타내는 자연수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 배열에 적힌 수를 나타내는 정수가 각각 N개씩 빈 칸을 사이에 두고 들어온다. 입력되는 정수는 www.acmicpc.net (1,1) ~ (N,N) 도달 중 만나는 수들을 곱할 때 뒤에 생기는 0의 최솟값을 구하는 문제다. 아이디어 : 뒤에 생기는 0의 개수라는 것은, 곧 2와 5의 개수 중 최솟값이라는 소리다. 따라서 2의 개수와 5의 개수에만 집중해보자. 최솟값을 구하려면, 2를 최소로 만들거나, 5를 최소로 만들어야 한다. 어떤 칸에 도달하려면, 위에서 내려오거나, 왼쪽에서 와야한다. 여기까지 dp식을 세울 ..