17136번: 색종이 붙이기
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크
www.acmicpc.net
- 생각
1x1. 2x2. 3x3, 4x4, 5x5 색종이로 10x10 사각형의 1인 부분을 최소의 색종이로 덮을 수 있는 수를 찾는 문제이다.
완벽한 정확도를 위해 모든 경우의 수를 돌리는 브루트포스 알고리즘으로 풀어야 겠다고 생각했다.
가장 큰 색종이부터 덮고 다시 덮은 부분을 되돌리면서 모든 경우의 수를 돌려보았다. (같은 크기의 색종이를 5번 이상 사용하면 안된다.)
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static int[][] array;
static int[] check;
static int answer;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
array = new int[10][10];
check = new int[5];
answer = Integer.MAX_VALUE;
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
array[i][j] = in.nextInt();
}
}
dfs(0);
if(answer == Integer.MAX_VALUE)
answer = -1;
}
private static void dfs(int y) {
if(CheckSuccess()) {
int count = 0;
for(int i = 0 ; i < 5 ; i++) {
count += check[i];
}
if(answer > count)
answer = count;
return;
}
for(int i = y ; i < 10 ; i++) {
for(int j = 0 ; j < 10 ; j++) {
if(array[i][j] == 1) {
for(int Size = 4 ; Size >=0 ; Size--) {
if(check[Size] < 5 && CheckSquare(i, j, Size)) {
check[Size]++;
CoverSquare(i, j, Size);
dfs(i);
UncoverSquare(i, j, Size);
check[Size]--;
}
}
return;
}
}
}
}
private static boolean CheckSquare(int y, int x, int Size) {
// 규격을 벗어나는 경우
if(x + Size >= 10 || y + Size >= 10) return false;
for(int i = y ; i <= Size + y ; i++) {
for(int j = x ; j <= Size + x; j++) {
if(array[i][j] == 0)
return false;
}
}
return true;
}
private static void CoverSquare(int y, int x, int Size) {
for(int i = y ; i <= Size + y ; i++) {
for(int j = x ; j <= Size + x; j++) {
array[i][j] = 0;
}
}
}
private static void UncoverSquare(int y, int x, int Size) {
for(int i = y ; i <= Size + y ; i++) {
for(int j = x ; j <= Size + x; j++) {
array[i][j] = 1;
}
}
}
private static boolean CheckSuccess() {
for(int i = 0 ; i < 10 ; i++) {
for(int j = 0 ; j < 10 ; j++) {
if(array[i][j] == 1)
return false;
}
}
return true;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- 조금 더 빠른 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static int[][] map;
static int[][] msize;
static boolean[][] cover;
static int[][] visit;
static int[] paper;
static int count;
static int answer;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
map = new int[10][10];
msize = new int[10][10];
visit = new int[10][10];
cover = new boolean[10][10];
paper = new int[6];
answer = Integer.MAX_VALUE;
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
map[i][j] = in.nextInt();
}
}
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
if(map[i][j] == 1) {
int count = 1;
loop:for(int k = 1; k <= 4; k++) {
for(int i2 = i; i2 <= i+k; i2++) {
for(int j2 = j; j2 <= j+k; j2++) {
if(i2 >= 10 || j2 >= 10 || map[i2][j2] != 1){
break loop;
}
}
}
count++;
}
msize[i][j] = count;
}
}
}
dfs(0,0);
if(answer == Integer.MAX_VALUE) answer = -1;
}
public static void dfs(int x, int y) {
int i = 0;
int j = 0;
if(answer <= count) return;
loop:for(i = x; i < 10; i++) {
for(j = 0; j < 10; j++) {
if(map[i][j] == 1 && !cover[i][j]) {
x = i;
y = j;
break loop;
}
}
}
if( i == 10 ) {
boolean check = true;
for(i = x; i < 10; i++) {
for(j = y; j < 10; j++) {
if(map[i][j] == 1 && !cover[i][j]) {
check = false;
}
}
}
if(check == true) {
if(answer > count) answer = count;
}
return;
}
//if(x >= 10 || y >= 10) return;
loop:for(i = msize[x][y]; i > 0; i--) {
if(visit[x][y] == 0 && paper[i]+1 <= 5) {
for(j = 0 ; j < i; j++) {
for(int k = 0; k < i; k++) {
if(cover[x+j][y+k] == true) {
continue loop;
}
}
}
visit[x][y] = i;
for(j = 0 ; j < i; j++) {
for(int k = 0; k < i; k++) {
cover[x+j][y+k] = true;
}
}
paper[i]++;
count++;
if(y == 9) dfs(x+1, 0);
else dfs(x, y+1);
count--;
paper[i]--;
visit[x][y] = 0;
for(j = 0 ; j < i; j++) {
for(int k = 0; k < i; k++) {
cover[x+j][y+k] = false;
}
}
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 2312번 : 수 복원하기 (0) | 2021.03.03 |
|---|---|
| [BOJ/JAVA] 백준 9421번 : 소수상근수 (0) | 2021.03.02 |
| [BOJ/JAVA] 백준 13977번 : 이항 계수와 쿼리 (0) | 2021.02.25 |
| [BOJ/JAVA] 백준 4963번 : 섬의 개수 (0) | 2021.02.24 |
| [BOJ/JAVA] 백준 5557번 : 1학년 (0) | 2021.02.23 |