[자바] 정올 1013 - Fivestar (java)

목차

문제 : jongol1013

 

풀이

  백준이 문닫은김에 오랜만에 생각나서 알고리즘 문제를 풀어보게 되었다.

확실히 머리론 대충 알겠는데 구현력이 떨어진게 맞는 것 같다. 아무래도 현업에서 재귀나 복잡한 for문 같은걸 쓸일이 없기도 하고, 요즘 워낙 LLM님이 구현을 잘해주셔서. 오랜만에 풀다보니 상당히 답답했다 ㅋㅋ

 

 

1. 일단 한 행만 있다고 생각해보자. (N=1)

A. *****.....
B. ..**..
C. .******..
D. .....

 

  이 경우 간단하다. 그냥 연속된 '*'을 세다가 5개 미만이면 불가능한 경우이다. A는 1개로 가능하고, B는 -1이고, C는 2개로 가능하고, D는 0개로 가능하다(-1 아님. 0개로 가능한거다.).

 

  만약 이 문제가 여기서 끝났다면 브론즈티어였을 것 같다.

아무튼 N이 4이하라면 그냥 이걸로 끝이다. 모든 행에 대해 행 단위로 세보면 끝이다.

 

 

2. 아직도 한 행만 있다고 생각해보자. 단, 특수기호 하나를 추가하자.

  임의로 '&'라는 기호를 하나 추가해보겠다. 여긴 '*' 처럼 막대를 놓을 순 있는데, 채워야하는 곳은 아니다.

A. &&&&*.....
B. *&&&&&&&&&
C. *&&&......

 

  무슨말이냐면, A의 경우 '*'을 하나 채우기위해 막대는 놓아야한다. 이 때 & 에도 막대를 놓을 수 있으니 1개로 가능하다.

B의 경우 '*'을 위해 막대를 놓아야하는데, '*'만 막대를 놓아도 된다. 즉 1개로 가능하다.

C의 경우 막대를 놓을 공간이 1칸 부족하니 -1이다.

 

  이 요구사항을 추가한다고 '1'에서 크게 어려워졌을까? 그렇진 않다. 다만 구현이 좀 더 귀찮아질 뿐이다. 예를들어

D. &&&*****..
E. &&*&*...

 

  D의 경우, 막대를 처음부터 놓아도 된다. 하지만 그 경우 '*'을 2개밖에 커버하지 못한다. [&&&**]***.. 이렇게 되니 손해이다. 따라서 처음부터 연속된 '&'은 무시하고, 그 다음 나온 '*'부터 막대를 놓는게 이득임을 알 수 있다. &&&[*****].. 이렇게.

 

  참고로 그리디 알고리즘에 따라 어차피 '*'을 덮을 수 없는 경우라면 불가능한 경우라서, 막대에 안덮힌 '*'이 있다면 무조건 거기부터 덮는게 항상 최소 개수임은 보장된다.

 

  아무튼 그렇다고 이걸 무조건 시도하면, E에서 문제가 생긴다. &&[*&*..]. 이렇게 되버린다.

이걸 구현하려면 상당히 귀찮은데, 일단 처음 나온 '*'부터 시작해서 5칸 가본 후 놓을 수 없다면, 그 이전 부분까지 다시 확인한다? 구현은 가능한데 귀찮다.

 

  그래서 입력받을 때 미리 연속된 '*'의 갯수를 세두면 편하다.

D는 [1,2,3,4,5,6,7,8,0,0]

E는 [1,2,3,4,5,0,0,0]

 

  이 경우 E의 경우에도 마찬가지로 &&[*&* 이렇게 시작되는 '*'부터 보다가, '.'을 만난 시점에 해당 위치의 연속된 갯수값 (5)을 보면 된다. 이게 5 미만이라면 불가능한 경우이다.

 

 

3. '1'과 '2'가 이해되었다면 이 문제를 쉽게 해결해볼 수 있다.

  만약 N이 6이상 가능했다면 난이도는 더 높았을텐데, N이 최대 5라서 출제자의 자비가 엿보인다.

N이 5일때만 세로로 놓을 경우의 수를 생각하면 된다. 그리고, 세로로 놓은 곳을 '2'에서 말한 '&' 인 곳이라고 보면 된다.

 

  '2'를 풀 수 있다고 가정하면, 그럼 이 문제는 그냥 세로로 연속 5개 '*'이 있는 위치에 대해 한번은 안놓고 돌리고, 한번은 놓고 돌리는 dfs 문제로 바뀐다.

A.
.*....
.*****
.*....
*****.
.*....


B.
.&....
.&****
.&....
*&***.
.&....

 

  즉 예제 문제의 경우, 한번은 세로로 안놓고 돌린다. A이고 이 경우 불가능하다.

한번은 세로로 놓고 돌린다. B이고 이 경우 3개로 가능하다.

세로로 연속 5개의 '*'이 있는 곳에 대해 이런식으로 완전탐색하면 된다. 그래봐야 2^10 번만 보면 되서 크게 문제되진 않는다.

 

 

코드 : github

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

public class Main {

    private static final int INF = 1000;
    private int r, c;
    private int[][] arr;
    private boolean[] vert;
    private int response = INF;

    private void solution(BufferedReader br) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        arr = new int[r][c];
        vert = new boolean[c];

        for (int i = 0; i < r; i++) {
            String s = br.readLine();

            int cnt = 0;
            for (int j = 0; j < c; j++) {
                boolean isStar = s.charAt(j) == '*';
                if (isStar) arr[i][j] = ++cnt;
                else cnt = 0;
            }
        }
        if (r != 5) cnt();
        else caseWork(0);

        System.out.println(response == INF ? -1 : response);
    }

    private void caseWork(int idx) {
        if (idx == c) {
            cnt();
            return;
        }

        boolean canVert = true;
        for (int i = 0; i < r; i++) {
            if (arr[i][idx] == 0) {
                canVert = false;
                break;
            }
        }

        caseWork(idx+1);

        if (!canVert) return;

        vert[idx] = true;
        caseWork(idx+1);
        vert[idx] = false;
    }

    private void cnt() {
        int result = 0;

        for (int i = 0; i < r; i++) {
            int cnt = cntRow(arr[i]);
            if (cnt == INF) return;

            result += cnt;
        }

        for (int i = 0; i < c; i++) if (vert[i]) result++;

        response = Math.min(response, result);
    }

    private int cntRow(int[] row) {
        int result = 0;

        int idx = 0;
        while (idx < c) {
            while (idx < c && (row[idx] == 0 || vert[idx])) idx++;

            if (idx == c) break;

            int limit = idx+5;
            while (idx < c && idx < limit && row[idx] != 0) idx++;

            if (row[idx-1] < 5) return INF;

            result++;
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        new Main().solution(new BufferedReader(new InputStreamReader(System.in)));
    }
}