[SW Expert Academy] 7673 영이는 영이 시져시져 [Java]

[ 핵심풀이 ]

첨에 dfs로 돌려서 시간초과가 나왔기때문에

프로그래머스 등굣길 문제와 같은 Dp개념으로 풀어야 시간초과가 나오지않는다!

4방향이 아닌, 2가지방향(상→하,좌→우)로만 움직이기때문에 계산은 간편하다!

 

배열중 어느한곳에있다면 상→하, 좌→우로

올 수 있는 두 가지 경우에 대해 2와 5의 개수가 적은값을 가져가면된다.

단, 첫줄의 상→하, 좌→우구간은 방문할 수 있는 경우의수가 1개이므로 비교하지 않아도된다.

 

1) 0이 나올수 있는 경우는 2와 5가 1개씩 생성될 때이므로 map의 모든숫자에 대해 2와 5로 소인수분해 해준다.

2) 맵이 0인경우는 가지않는다

3) 시작부분은 가지않는다

4) 시작부분에 걸친 세로, 가로줄은 2가지 방향을 비교하지 않고 1가지 방향에 대해서만 처리한다

5) 나머지부분은 2가지방향에서 2와 5를 가진 최소값을 비교하여 더 작은쪽을 가져온다.

 

문제가 좀 하자가많다. 테케도 고려되지않고, 풀이도 비슷비슷한 모습이많아 어떻게 처리될 지 모르겠다.

문제 테케중

1
6
1 5 5 2 0 0
2 0 0 2 0 0
2 2 5 1 5 5
0 0 0 0 0 5
0 0 0 0 0 5
0 0 0 0 0 1

정답 ) 2

오답 ) 3

인 경우가있다. 단순하게보면 거꾸로 시작하면되겠지만,

둘을 제대로 비교하기위해선 완탐이 필요하다고 생각한다.

문제에서 별다른 조건이없고.... 백준처럼 피드백을 받지않아 잘 모르겠다.

프로그래머스 등굣길 문제를 푸는것을 더 추천한다.

[ Java ]

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

public class _7673_영이는_영이_시져시져 {
    static final int MAX = 1010;
    static int N;
    static int map[][] = new int[MAX][MAX];
    static int _2[][] = new int[MAX][MAX];
    static int _5[][] = new int[MAX][MAX];
	
    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int t=1;t<=tc;t++) {
            N = Integer.parseInt(br.readLine());
			
            for(int i=1;i<=N;i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=1;j<=N;j++)
                    map[i][j] = Integer.parseInt(st.nextToken());
            }
            mapset();
            System.out.print("#"+t+" ");
            solve();
        }
    }
    static void mapset() {
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) {
                if (map[i][j] == 0) {
                    _2[i][j] = 987654231;
                    _5[i][j] = 987654321;
                    continue;
                }
                int v2 = 0;
                int v5 = 0;
                int temp = map[i][j];
                while(temp%5==0) {
                    temp/=5;
                    v5++;
                }
                while(temp%2==0) {
                    temp/=2;
                    v2++;
                }
                _2[i][j] = v2;
                _5[i][j] = v5;
            }
    }
    static void solve() {
        for(int i=N;i>=1;i--)
            for(int j=N;j>=1;j--) {
                if (map[i][j] == 0) continue;
                if (i==N && j==N) continue;
                if (i==N) {
                    _2[i][j] = _2[i][j] + _2[i][j+1];
                    _5[i][j] = _5[i][j] + _5[i][j+1];
                    continue;
                }
                if (j==N) {
                    _2[i][j] = _2[i][j] + _2[i+1][j];
                    _5[i][j] = _5[i][j] + _5[i+1][j];
                    continue;
                }
				
                int l2 = _2[i][j]+_2[i][j+1];
                int l5 = _5[i][j]+_5[i][j+1];
                int u2 = _2[i][j]+_2[i+1][j];
                int u5 = _5[i][j]+_5[i+1][j];
                int left = Math.min(l2, l5);
                int up = Math.min(u2, u5);
                if (left < up) {
                    _2[i][j] = l2;
                    _5[i][j] = l5;
                }
                else {
                    _2[i][j] = u2;
                    _5[i][j] = u5;
                }
            }
        System.out.println(Math.min(_2[1][1], _5[1][1]));
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        init();
    }
}