kingsubin

import java.io.*;
import java.util.*;
 
public class boj_18808 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m, k, ans;
    static int[][] board;
    static int[] startPoint;
    static List<int[][]> stickers = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        input();
        solve();
        printAns();
    }
 
    static void solve() {
        // 모든 스티커에 대해서 검사
        for (int[][] sticker : stickers) {
            // 스타트 가능한 부분 찾기, (0, 0) ~ (maxXSize, maxYSize)
            int[] canStartDotMax = findDot(sticker);
 
            // 가능한 부분인지 확인하기 -> 가능하다면 startPoint 에 시작하는 x, y 좌표 담음
            boolean possibleToStart = isPossibleToStart(canStartDotMax, sticker);
 
            if (possibleToStart) {
                // 스티커 붙이기
                attachSticker(sticker); // startPoint[] static 주의
            } else {
                // 스티커 회전하기 90, 180, 270도
                for (int turnCount = 1; turnCount <= 3; turnCount++) {
                    int[][] turnSticker = rotate(turnCount, sticker);
 
                    int[] dot = findDot(turnSticker);
                    if (isPossibleToStart(dot, turnSticker)) {
                        attachSticker(turnSticker); // startPoint[] static 주의
                        break; // 이미 스티커를 붙였다면 다음 스티커로 넘어감
                    }
                }
            }
        }
    }
 
    static int[][] rotate(int turnCount, int[][] sticker) {
        // do turn, turnCount 1 - 90, 2 - 180, 3 - 270 도
        int row = sticker.length;
        int col = sticker[0].length;
        int[][] turnSticker;
 
        // 회전시키기
        if (turnCount == 1) { // 90
            turnSticker = new int[col][row];
            for (int i = 0; i < col; i++) {
                for (int j = 0; j < row; j++) {
                    turnSticker[i][j] = sticker[row-1-j][i];
                }
            }
        } else if (turnCount == 2) { // 180
            turnSticker = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    turnSticker[i][j] = sticker[row-1-i][col-1-j];
                }
            }
        } else { // 270
            turnSticker = new int[col][row];
            for (int i = 0; i < col; i++) {
                for (int j = 0; j < row; j++) {
                    turnSticker[i][j] = sticker[j][col-1-i];
                }
            }
        }
        return turnSticker;
    }
 
    static void attachSticker(int[][] sticker) {
        int x = startPoint[0];
        int y = startPoint[1];
        int row = sticker.length;
        int col = sticker[0].length;
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (sticker[i][j] == 1) {
                    board[i + x][j + y] = sticker[i][j];
                }
            }
        }
    }
 
    static boolean checkPoint(int x, int y, int[][] sticker) {
        int row = sticker.length;
        int col = sticker[0].length;
 
        boolean flag = true;
        all : for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (sticker[i][j] == 0) continue;
                if (board[i + x][j + y] == 1) { // 이미 스티커가 붙여져있으면
                    flag = false;
                    break all;
                }
            }
        }
        return flag;
    }
 
    static boolean isPossibleToStart(int[] now, int[][] sticker) {
        int maxX = now[0];
        int maxY = now[1];
 
        if (maxX < 0 || maxY < 0) return false;
 
        // 0 ~ maxX , 0 ~ maxY
        boolean flag = false;
        all : for (int startX = 0; startX <= maxX; startX++) {
            for (int startY = 0; startY <= maxY; startY++) {
 
                // 시작포인트에서 스티커를 붙일 수 있는가 를 확인
                if (checkPoint(startX, startY, sticker)) {
                    startPoint = new int[] { startX, startY };
                    flag = true;
                    break all;
                }
            }
        }
        return flag;
    }
 
    static int[] findDot(int[][] sticker) {
        int xSize = sticker.length;
        int ySize = sticker[0].length;
 
        // find startDot
        int maxXSize = n - xSize;
        int maxYSize = m - ySize;
        return new int[] { maxXSize, maxYSize };
    }
 
    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        board = new int[n][m];
 
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            int[][] sticker = new int[a][b];
 
            for (int j = 0; j < a; j++) {
                st = new StringTokenizer(br.readLine());
                for (int l = 0; l < b; l++) {
                    sticker[j][l] = Integer.parseInt(st.nextToken());
                }
            }
 
            stickers.add(sticker);
        }
    }
 
    static void printAns() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) ans++;
            }
        }
        System.out.println(ans);
    }
}

 

- 시뮬레이션

- 어려움

 

- 어제도 고민하고 오늘도 계속 붙잡아서 겨우 성공 

- 접근 자체가 생각이 안나는건 아니고 생각한걸 코드로 짜내는 과정이 어려웠음

 

1. 스티커를 list에 저장

2. 스티커의 제일 끝을 기준으로 스티커를 붙일 수 있는 최대 시작 포인트의 x, y 좌표 저장  canStartDotMax

3. 0~최대X, 0~최대Y 값을 기준으로 붙일 수 있는지 확인  isPossibleToStart 

4. 가능 하다면 스티커 붙이기 attachSticker

5. 불가능하다면 90, 180, 270도 순서로 회전 시킨후 위의 과정 반복 rotate

 

 

 

 

---

www.acmicpc.net/problem/18808