[BOJ] 18808. 스티커 붙이기

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

18808번: 스티커 붙이기

 

 

1. 해결방법

일단 시뮬레이션 문제인데, 어려워서 혼자서는 풀지 못하였다. 바킹독님 영상보고 해결 방법에 대해 도움을 받았는데도 4시간이 넘게 걸렸다,,,,,,,

중요한 부분은
1. 노트북에 모눈종이를 비교했을 때, 스티커를 붙일 수 있는지에 대한 체크를 먼저 해야한다.
2. 스티커를 붙이지 못했을 때, 90도 회전을 해야한다.(4번 반복)

flag라는 변수를 사용해서 스티커르 붙일 수 있는지에 대한 체크를 해두었고, 붙일 수 없다면 90도 회전하는 함수를 추가 작성하였다.
여기서 출력할 때, 스티커를 붙이는데 그래프의 1이 최소 또는 최대의 값을 구하는 것이 아니라 순서대로 붙이는데 붙일 수 없다면 그 때 회전하는 방식이다. 즉, 최소 또는 최대가 아닌 설명과 코드가 길지만 단순 시뮬레이션에 해당하는 문제이다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline
from copy import deepcopy

# input
N, M , K = map(int, input().split())
maps = [[0] * M for _ in range(N)]

stickers = []
for _ in range(K):
    R, C = map(int, input().split())
    stickers.append([list(map(int, input().split())) for _ in range(R)])


# 회전
def rotate(sticker):
    len_r, len_c = len(sticker), len(sticker[0])
    temp = [[0] * len_r for _ in range(len_c)]

    for i in range(len_r):
        for j in range(len_c):
            temp[j][len_r - i - 1] = sticker[i][j]
    return temp


# 스티커 가능한지 체크
def possible(y, x, sticker):
    global maps

    r, c = len(sticker), len(sticker[0])
    for i in range(r):
        for j in range(c):
            if maps[y + i][x + j] == 1 and sticker[i][j] == 1:
                return False

    for i in range(r):
        for j in range(c):
            if sticker[i][j] == 1:
                maps[y + i][x + j] = 1
    return True


# main
for sticker in stickers:
    for _ in range(4):
        r, c = len(sticker), len(sticker[0])
        flag = False    # 스티커를 붙였는가?
        # 노트북에 모눈종이 스티커를 붙일 수 있는지 체크
        for row in range(N - r + 1):
            for col in range(M - c + 1):
                if possible(row, col, sticker) == True:
                    flag = True
                    break
            if flag == True:
                break
        if flag == True:
            break
        else:
            # 스티커를 못붙였다면, 90도 회전
            sticker = rotate(sticker)

answer = 0
for i in range(N):
    for j in range(M):
        if maps[i][j] == 1:
            answer += 1

print(answer)