[ boj : 23562 ] ㄷ 만들기

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

23562번: ㄷ 만들기

해설 : 단순 구현문제입니다. 그냥 모오오오오오오오오오든 경우의 수를 전부 해보면 됩니다.

 

크기가 1인 정사각형부터 시작해서 board 보다 크기가 커질때까지 count 해줍시다.

 

먼저 #의 개수를 전부 세줍시다.=>black

현재 (x,y) 에서 시작해서 ㄷ 모양을 탐색해 주면서 . 이면 #으로 바꾸어 줘야하니 count 해주고,

답을 갱신할때는 (a*count) + ((black + count) - (size*size*7))*b 라는 식을 이용해 줄 수 있겠죠.

 

//package com.boj.practice;
/**
 * IO Template reference : 류호석
 */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    static FastReader scan = new FastReader();

    static int n, m, a, b;
    static String[] board;
    static int black = 0;

    public static void main(String[] args) throws IOException {
        int t = 1;
        //t = scan.nextInt();
        while (t-- > 0)
            solve();
    }

    static void solve() throws IOException {
        n = scan.nextInt();
        m = scan.nextInt();
        a = scan.nextInt();
        b = scan.nextInt();
        board = new String[n];
        for (int i = 0; i < n; i++) {
            board[i] = scan.nextLine();
            for (int j = 0; j < m; j++) {
                if (board[i].charAt(j) == '#')
                    black++;
            }
        }
        int ans = (int) 1e9;
        for (int i = 1; ; i++) {
            int ret = go(i);
            if (ret >= (int) 1e9) break;
            ans = min(ans, ret);
        }
        scan.write(Integer.toString(ans));
        scan.flush();
    }

    static int go(int size) {
        int ret = (int) 1e9;
        for (int i = 0; i < n; i++) {
            if (i + (size * 3 - 1) >= n) break;
            for (int j = 0; j < m; j++) {
                if (j + (size * 3 - 1) >= m) break;
                int num = paint(i, j, size);
                ret = min(ret, a * num + ((black + num) - (size * size * 7)) * b);
            }
        }
        return ret;
    }

    static int paint(int x, int y, int size) {
        int cnt = 0;
        //위
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + (size * 3); j++) {
                if (board[i].charAt(j) == '.')
                    cnt++;
            }
        }
        //중간
        for (int i = x + size; i < x + (size * 2); i++) {
            for (int j = y; j < y + size; j++) {
                if (board[i].charAt(j) == '.')
                    cnt++;
            }
        }
        //아래
        for (int i = x + (size * 2); i < x + (size * 3); i++) {
            for (int j = y; j < y + (size * 3); j++) {
                if (board[i].charAt(j) == '.')
                    cnt++;
            }
        }
        return cnt;
    }

    static class FastReader {
        BufferedReader br;
        BufferedWriter bw;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        void write(String str) throws IOException{
            bw.write(str);
        }
        void flush() throws IOException{
            bw.flush();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}