(문제)
https://www.acmicpc.net/problem/18808
18808호: 스티커 붙이기
혜윤은 최근 각종 대회에 참가하면서 노트북에 붙일 스티커를 많이 받았다.
스티커는 아래와 같이 정사각형 모눈 종이에 인쇄되며, 스티커의 각 패널은 수직 및 수평으로 연결됩니다.
www.acmicpc.net
(문제를 해결하다)
이 문제는 간단한 구현 문제였습니다.
다 풀고 코드를 보니 별로 어렵지는 않은 것 같았는데 개인적으로 구현이 정말 복잡하고 머리가 아팠습니다.
구현은 다음과 같습니다.
1. 목록에 있는 모든 스티커를 2차원 배열로 저장합니다.
2. 노트북을 nxm의 2차원 배열로 만듭니다.
3. 왼쪽 위부터 순서대로 노트북에 붙일 수 있는지 여부를 판단합니다.
4. 가능하면 랩탑에 테이프로 붙입니다.
5. 해당하는 경우 7단계로 이동합니다.
그렇지 않은 경우 오른쪽으로 90도 회전하고 3단계와 4단계를 다시 수행합니다.
6. 모든 설명을 확인하고 첨부할 수 없는 경우 건너뛰고 7단계로 이동합니다.
7. 다음 스티커를 확인합니다.
** 노트북을 넘길 때 스티커의 크기를 고려해야 합니다.
(그렇지 않으면 색인이 생략됩니다.
) 즉, 노트의 오른쪽 하단이 스티커의 오른쪽 하단이 되어야 합니다.
** 구현 문제를 해결하는 가장 쉬운 방법은 메서드를 만드는 것 같습니다.
사실 방법을 분류하기가 애매한데, 복잡하지 않아서 보기도 쉽고 풀기도 쉽습니다.
다음 코드를 보면 이해하기 쉽습니다.
(암호)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String() args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int()() noteBook = new int(n)(m);
List<int()()> stickerList = new ArrayList<>();
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int()() sticker = new int(r)(c);
for (int j = 0; j < r; j++) {
st = new StringTokenizer(br.readLine());
for (int q = 0; q < c; q++) {
sticker(j)(q) = Integer.parseInt(st.nextToken());
}
}
stickerList.add(sticker);
}
for (int()() sticker : stickerList) {
for (int i = 0; i < 4; i++) {
if (checkAndAttach(noteBook, sticker)) {
break;
}
sticker = rotateSticker(sticker);
}
}
int count = 0;
for (int i = 0; i < noteBook.length; i++) {
for (int j = 0; j < noteBook(i).length; j++) {
if (noteBook(i)(j) == 1) count++;
}
}
bw.write(count + "");
br.close();
bw.flush();
bw.close();
}
public static int()() rotateSticker(int()() sticker) {
int rowSize = sticker.length;
int colSize = sticker(0).length;
int()() result = new int(colSize)(rowSize);
for (int i = 0; i < sticker.length; i++) {
for (int j = 0; j < sticker(i).length; j++) {
result(j)(rowSize - i - 1) = sticker(i)(j);
}
}
return result;
}
public static boolean checkAndAttach(int()() noteBook, int()() sticker) {
for (int i = 0; i <= noteBook.length - sticker.length; i++) {
for (int j = 0; j <= noteBook(0).length - sticker(0).length; j++) {
if (check(i, j, noteBook, sticker)) {
attach(i, j, noteBook, sticker);
return true;
}
}
}
return false;
}
public static boolean check(int x, int y, int()() noteBook, int()() sticker) {
for (int i = 0; i < sticker.length; i++) {
for (int j = 0; j < sticker(0).length; j++) {
if (sticker(i)(j) + noteBook(i + x)(j + y) >= 2) {
return false;
}
}
}
return true;
}
public static void attach(int x, int y, int()() noteBook, int()() sticker) {
for (int i = 0; i < sticker.length; i++) {
for (int j = 0; j < sticker(i).length; j++) {
noteBook(i + x)(j + y) += sticker(i)(j);
}
}
}
}