[ boj : 23562 ] ㄷ 만들기

[ boj : 23562 ] ㄷ 만들기

728x90

https://www.acmicpc.net/problem/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; } } }

728x90

from http://boomrabbit.tistory.com/205 by ccl(A) rewrite - 2021-12-13 21:28:11