백준 1369번: 배열값

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

 

주어진 n x n 배열에 대해서 (0,0)부터 (n-1, n-1)까지 오른쪽, 아래 방향으로만 배열값이 0이 아닌 곳만 이동하면서 곱할 때 맨 끝에 연속된 0의 갯수의 최솟값을 구하는 문제이다. 전부 곱하면 숫자가 너무 커지므로 맨 끝애 0이 생길 경우인 2와 5의 곱의 수의 최솟값이 0의 갯수의 최솟값임을 파악한 후 이를 dp로 최솟값을 누적하여 구하였다.

 

우선, 각 배열값의 2의 곱 수, 5의 곱 수를 구한다. 각 숫자로 나누어 떨어지지 않을 때 까지 while문으로 갯수를 세었다.

private static int getFactorCount(int val, int factor) {
    int count = 0;
    while (val > 0 && val % factor == 0) {
        count++;
        val /= factor;
    }
    return count;
}

int[][] count2 = new int[n][n];
int[][] count5 = new int[n][n];

for (int i = 0; i < n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int j = 0; j < n; j++) {
        int val = Integer.parseInt(st.nextToken());
        if (val == 0) {
            count2[i][j] = 100000000;
            count5[i][j] = 100000000;
        } else {
            count2[i][j] = getFactorCount(val, 2);
            count5[i][j] = getFactorCount(val, 5);
        }
    }
}

 

 

이후, dp로 (0, 0)에서 (n-1, n-1)까지 2와 5 각각의 최소 포함 갯수를 누적하여 구한 후 두 개수의 최솟값이 0의 갯수의 최솟값이다.

private static int getMinimumZero(int n, int[][] counts) {
    int[][] dp = new int[n][n];
    dp[0][0] = counts[0][0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + counts[i][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + counts[0][j];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + counts[i][j];
        }
    }
    
    return dp[n - 1][n - 1];
}

System.out.print(Math.min(getMinimumZero(n, count2), getMinimumZero(n, count5)));

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 배열값1369 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] count2 = new int[n][n];
        int[][] count5 = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int val = Integer.parseInt(st.nextToken());
                if (val == 0) {
                    count2[i][j] = 100000000;
                    count5[i][j] = 100000000;
                } else {
                    count2[i][j] = getFactorCount(val, 2);
                    count5[i][j] = getFactorCount(val, 5);
                }
            }
        }
        
        System.out.print(Math.min(getMinimumZero(n, count2), getMinimumZero(n, count5)));
    }
    
    private static int getFactorCount(int val, int factor) {
        int count = 0;
        while (val > 0 && val % factor == 0) {
            count++;
            val /= factor;
        }
        return count;
    }
    
    private static int getMinimumZero(int n, int[][] counts) {
        int[][] dp = new int[n][n];
        dp[0][0] = counts[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + counts[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + counts[0][j];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + counts[i][j];
            }
        }
        
        return dp[n - 1][n - 1];
    }
}