글 읽기 - 예제 2번이 도저히 이해가 안됩니다.

rlarudgh2017 1년 전 0

예제 2번의 출력이 3이 되어야 하지 않나요? 노트북의 크기가 가로로 3칸이고 스티커 중에 세로로 3칸인걸 회전시키면 3칸에 딱 맞는다고 생각합니다. 아래는 제 코드입니다.

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
laptop = [[0] * m for _ in range(n)]
stickers = []
ans = 0
for _ in range(k):
    i, j = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(i)]
    stickers.append(sticker)

def rotate_2d(arr):
    new = [[0] * len(arr) for _ in range(len(arr[0]))]
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            new[j][len(arr) - 1 - i] = arr[i][j]
    return new

def inRange(y, x):
    if 0 <= y < n and 0 <= x < m:
        return True
    return False

def possible(y, x, sticker):
    for i in range(len(sticker)):
        for j in range(len(sticker[0])):
            if not inRange(y + i, x + j) or (laptop[y + i][x + j] == 1 and sticker[i][j] == 1):
                return False
    return True

def attatch(y, x, sticker):
    for i in range(len(sticker)):
        for j in range(len(sticker[0])):
            if sticker[i][j] == 1:
                laptop[y + i][x + j] = 1

def detatch(y, x, sticker):
    for i in range(len(sticker)):
        for j in range(len(sticker[0])):
            if sticker[i][j] == 1:
                laptop[y + i][x + j] = 0

def dfs(depth):
    global ans
    if depth >= len(stickers):
        cnt = 0
        for i in range(n):
            for j in range(m):
                if laptop[i][j] == 1:
                    cnt += 1
        ans = max(ans, cnt)
        return
    sticker = stickers[depth]
    for i in range(n):
        for j in range(m):
            for _ in range(4):
                sticker = rotate_2d(sticker)
                if not possible(i, j, sticker):
                    continue
                attatch(i, j, sticker)
                dfs(depth + 1)
                detatch(i, j, sticker)
    dfs(depth + 1)

dfs(0)
print(ans)

dldbgh1004 1년 전 0

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

예제 2번의 경우 2번째 스티커를 먼저 붙였기 때문에 3번째 스티커를 붙일 수 없습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제 2번이 도저히 이해가 안됩니다.

rlarudgh2017 1년 전 0

dldbgh1004 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말